Semi-systolic architecture for decoding error-correcting codes

A decoder for decoding a digital data stream into an updated stream, the digital data stream comprising a plurality of data words in sequency, the digital data stream encoded according to a linear error-correcting code, and the linear error-correcting code having a regular structure which can be specified by coefficients of a polynomial, the decoder comprising:

• at least one parity processing means, coupled to receive as input the digital data stream encoded according to the linear error-correcting code, for generating a parity data stream, said at least one parity processing means including a first broadcast input bus and a first shift register means, wherein said first shift register means comprises a ring of serially coupled registers holding data words, and wherein selected registers of said first shift register means include exclusive-OR combining means for combining data from said first broadcast input bus and said data words;
• and
• at least one update processing means, coupled to receive as input data said parity data steam, said at least one update processing means including a second broadcast input bus and a second shift register means, wherein said second broadcast bus is coupled to a serial output of said at least one parity processing means, wherein said second shift register means comprises a ring of serially coupled registers holding data words, and wherein selected registers of said second shift register means include arithmetic element means for combining data from said second broadcast input bus and said data words in said second shift register means.

A decoder for decoding a digital data stream encoded according to a quasi-cyclic error-correcting code generated from a convolutional code, said decoder comprising:

• at least one parity processing means, said at least one parity processing means coupled to receive as input, in n parallel information paths and p parallel parity paths, said digital data stream containing data encoded according to the quasi-cyclic error-correcting code, for generating a parity data stream, said parity data steam comprising a plurality of computed parities, each computed parity resulting from the operation of a set of parity equations on a selection of data words of the digital data stream, said selection of data words determined by the quasi-cyclic error-correcting code, said at least one parity processing means comprising a first plurality of shift registers coupled in a first serial pipeline with the last shift register in said first serial pipeline coupled back to the first register in said first serial pipeline, thereby forming a first recirculating data loop;
• and
• at least one update processing means, said at least one update processing means coupled to receive, in n parallel information paths and p parallel parity paths, said parity data stream and said digital data stream as time-delayed input data, said at least one update processing means for computing a modified data stream based on data form said parallel information paths, said parallel parity paths, wherein the modification of the data in said modified data stream comprises an updated reliability value and an updated data value of each data word form the digital data stream, said update reliability value and said updated data value computed according to the quasi-cyclic error-correcting code by said at least one update processing means, said at least one update processing means also comprising a second plurality of shift registers coupled in a second serial pipeline with the last shift register in said second serial pipeline coupled back to the first register in said second serial pipeline, thereby forming a second recirculating data loop.