Apparatus for fast decoding of a non-linear code

• US 4,896,353 A
• Filed: 09/23/1988
• Issued: 01/23/1990
• Est. Priority Date: 09/23/1988
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Dehgani, Ayyoob A., Rushforth, Craig K.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US07/248,866
• Time in Patent Office: 487 Days
• Field of Search: 375/1, 380/28, 380/6, 340/825.69, 341/75, 341/107
• US Class Current: 714/755
• CPC Class Codes: H04L 1/0052 Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0065 Serial concatenated codes

Abstract

The present invention provides a high-speed decoder for decoding signals encoded into Nordstrom-Robinson 16,256,6 non-linear code. The novel decoder receives a transmitted encoded signal in the form of a multi-dimensional vector to be decoded. The decoder comprises a plurality of computing elements coupled to the input encoded signals and produces modified multi-dimensional vectors and subcode values which are decoded in a plurality of subcode decoders to produce intermediate inner product values and information words associated with the intermediate inner product values. The intermediate inner product values are compared in comparator means to provide the maximum intermediate inner product value and its associated information which is indicative of the best mathematical estimate of the encoded signal being decoded.

Claims

1. A high-speed decoder for decoding Nordstrom-Robinson encoded information comprising:

a source of encoded signals in the form of multi-dimensional vectors (r) to be decoded,

a plurality of computing elements coupled to said source of encoded signals,

each said computing element having means for modifying said multi-dimensional vectors (r) and for producing subcode values (S_K),

a plurality of subcode decoders coupled to said computing elements for producing an intermediate inner product (ip) value and an associated information bit value indicative of said intermediate inner product value, and a plurality of comparators each being coupled to the output of one of said subcode decoders for comparing said intermediate inner product values and for determining the maximum intermediate inner product and the information bits indicative of the maximum inner product, and

output means coupled to said comparators for producing said information bits as a digital output indicative of the best mathematical estimate of the encoded signal being decoded.

2. A high-speed decoder as set forth in claim 1 wherein said digital information bits are indicative of a Nordstrom-Robinson word previously encoded.

3. A high-speed decoder as set forth in claim 1 wherein said subcode decoder comprises an adder coupled to a subtractor for producing said intermediate inner product values.

4. A high-speed decoder as set forth in claim 3 where said subcode decoder further comprises a parity checker coupled to a sign input of the subcode value for producing said digital output indicative of said intermediate inner product value.

5. A high-speed decoder as set forth in claim 1 wherein said plurality of computing elements are coupled in series in a systolic array.

6. A high-speed decoder as set forth in claim 5 wherein said plurality of said subcode decoders are each coupled in series between a comparator and a computing element.

7. A high-speed decoder as set forth in claim 1 wherein said pluraity of computing elements are comprised of precomputing elements arranged in parallel.

8. A high-speed decoder as set forth in claim 7 wherein said plurality of computing elements comprise means for storing the output of said precomputing elements and for producing said subcode value outputs.

9. A high-speed decoder as set forth in claim 8 wherein said plurality of subcode decoders are connected in parallel to the outputs of said means for storing the outputs from said precomputing elements.

10. A high-speed decoder as set forth in claim 9 wherein said plurality of comparators comprise a bank of comparators connected to the outputs of said subcode decoders for producing a maximum inner product information bits at the output.

11. A high-speed decoder for decoding Nordstrom-Robinson encoded information in the presence of additive whit Gaussian noise, comprising:

a plurality of processing elements coupled in series to form a systolic array,

the first processing element in said systolic array having a signal input comprising a multi-dimensional vector of real numbers to be decoded,

the last processing element of said systolic array having a digital output defining the best estimate of the Nordstrom-Robinson encoded information codeword,

intermediate processing elements,

said processing element having means for modifying a received multi-dimensional vector and means for computing a subcode value,

subcode decoder means coupled to the output of said means for modifying a dimensional vector and for generating an intermediate inner product value and an associated information word indicative of the intermediate inner product,

comparison means coupled to the output of said subcode decoder means and the preceeding processing element for producing an output indicative of the largest intermediate inner product input, and

memory means responsive to said largest intermediate inner product produced by said last processing element for producing a digital output of the encoded information input.