Method and apparatus for encoding and decoding digital signals

A method of decoding a sequence of codeword vectors formed by encoding a sequence of digital words, each having a first portion and a second portion, by the sequential steps of, using a trellis code, successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words, using each trellis-encoded word to select a corresponding one of a plurality of subcodes of a block code each comprising a coset of a Reed-Muller code, and using the selected subcode to encode the second portion of the corresponding digital word;

• the method of decoding comprising the steps of:
• operating upon each of the codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct;
• using a trellis decoder, operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions;
• and
• associating with each of the estimated first portions the corresponding estimated second portion thereby providing a sequence of output digital words corresponding to the sequence of digital words originally encoded, wherein the step of operating upon each of the codeword vectors includes the steps of applying to each codeword vector a coset leader for each of the cosets, and performing a Fast Hadamard Transform upon the resulting vector, and the step of operating upon the sequence of likelihood metrics and associated estimated second portions comprises applying a Viterbi algorithm thereto.

Apparatus for encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, supplying the sequence of codewords to a transmission or storage medium, extracting a corresponding sequence of codeword vectors from the transmission or storage medium, and decoding the sequence of codeword vectors to extract the originally-encoded sequence of digital words;

• the apparatus comprising an encoder comprising:
• a trellis code unit for successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words;
• a block code unit responsive to the trellis-encoded words for encoding respective second portions of the digital words to provide codewords from selected ones of subcodes of the block code, each subcode comprising a coset of a Reed-Muller code, the coset used for a particular second portion being determined by the trellis-encoded word obtained by encoding the corresponding first portion;
• the apparatus further comprising a decoding unit comprising;
• means for operating upon each of the sequence of codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct;
• a trellis decoder unit having means for operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions;
• and
• means for associating with each of the estimated first portions the corresponding estimated second portion thereby to provide a sequence of output digital words corresponding to the sequence of digital words originally encoded.

A decoding apparatus for decoding codeword vectors produced by encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, the sequence of codewords being supplied to a transmission or storage medium, and extracted as a corresponding sequence of codeword vectors from the transmission or storage medium, the codewords being encoded by, using a trellis code, successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words;

• using each trellis-encoded word to select a corresponding one a plurality of subcodes of a block code;
• and using the selected subcode to encode the second portion of the corresponding digital word, the block code comprising subcodes each constituted by one of a plurality of cosets of a Reed-Muller code;
• the decoding unit comprising;
• means for operating upon each of the codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct, the decoder using a Fast Hadamard Transform;
• a trellis decoder unit having means using a Viterbi algorithm for operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions;
• and
• means for associating with each of the estimated first portions the corresponding estimated second portion thereby to provide a sequence of output digital words corresponding to the sequence of digital words originally encoded.