REPLICATION DECODING

Any symbol in a redundant code can be recovered when it belongs to certain erasure patterns Several alternative expressions of a given symbol, to be referred to as its replicas, can therefore be computed in terms of other ones. Decoding is interpreted as decoding upon a received symbol, given itself and a number of such replicas, expressed in terms of other received symbols. For linear q-ary (n, k) block codes, soft-decision demodulation and memoryless channels, the maximum-likelihood k decision rule on a given symbol is formulated in terms of r ≤n-k independent replicas from the parity-check equations. All replicas deriving from the r selected replicas by linear combination are actually taken into account in this decision rule. Its implementation can be direct; use transformations or a sequential circuit implementing a trellis representation of the parity-check matrix. If r = n– k, decoding is optimum, in the sense of symbol-by-symbol maximum-likelihood. Simplification results in the transformed and sequential implementations when r <n– k. If the selected replicas are disjoint, generalized (q-ary, weighted) threshold decoding results. The decoding process can easily be modified in order to provide word-by-word maximum-likelihood decoding. Convolutional codes are briefly considered. Two specific problems are discussed: the use of previous decisions, which leads to a weighted generalization of feedback decoding, and the extension of replication decoding to nonsystematic codes. © 1979 IEEE