# US 4,397,022 A · Weighted erasure codec for the (24, 12) extended Golay code

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 4,397,022 A
- Document ID: US4397022A
- Status: Granted
- Kind: A
- Application number: 06/230,136
- Filed: 1981-01-30
- Granted: 1983-08-02
- Earliest claimed: 1981-01-30
- Inventors: Ming-I. Weng; Lin-Nan Lee
- Web page: https://patentgrep.com/patent/US4397022A

## CPC

- H03M 13/15: Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes (H03M13/17 takes precedence)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

A codec consists of an encoder and decoder. The encoder provides 12 information bits, 11 parity bits generated according to the polynomial for the (23, 12) Golay code, and an overall parity bit to a transmitter at selected transmit times to form a 24-bit block of data. The decoder is separated into two independent list decoders, a comparator, and common clock generator and output buffers. Each list decoder is divided into a syndrome generator and an overall parity check generator, a syndrome error pattern table, an input buffer, error correction logic, and four-error detection logic. The error pattern table includes a pair of read only memories storing the most likely 12-bit error patterns at each ROM address corresponding to each syndrome. An additional 4-bit output is used to indicate the number of errors in the associated error pattern. The comparator compares the number of errors detected in the two independent decoders and chooses the decoder having the fewer number of errors to provide the corrected data.

## Claims

### Claim 1

An error correcting decoder for receiving a plurality of data bits, at least a portion of said data bits being generated in accordance with a predetermined function, said data bits including information bits and coding bits, said decoder comprising:
generator means for processing said data bits in accordance with said predetermined function to produce a generator output;
memory means receiving said generator output for producing an error pattern in response thereto, said error pattern providing a direct indication of which of said information bis are incorrect; and
correction means for correcting said information bits in accordance with said error pattern.

### Claim 2 (depends on 1)

The decoder of claim 1 wherein said correction means comprises logic means having first and second logic inputs, said logic means providing an exclusive OR function, at least a portion of said data bits being applied to said first logic input, said error pattern being applied to said second logic input.

### Claim 3 (depends on 2)

The decoder of claim 2 wherein said generator means comprises a syndrome generator for providing a generator output according to the polynomial
g(x)=1+x+x.sup.5 +x.sup.6 +x.sup.7 +x.sup.9 +x.sup.11
for the (23, 12) Golay code, whereby said correction means can correct as many as three errors.

### Claim 4 (depends on 3)

The decoder of claim 3 wherein said memory means further produces an error indication indicative of the number of errors detected up to as many as three errors.

### Claim 5 (depends on 4)

The decoder of claim 4 wherein said generator means further comprises an overall parity generator for generating a parity bit based on said plurality of data bits to thereby enable said decoder to detect as many as four errors.

### Claim 6 (depends on 5)

The decoder of claim 5 further comprising means for disabling said correction means upon detecting at least four errors.

### Claim 7 (depends on 1, 2, 3, 4, 5, 6)

The decoder of any one of claims 1-6 wherein said memory means comprises:
read only memory (ROM) means having an address input and data output, said generator output being applied to said address input, and said data output directly providing said error pattern.

### Claim 8 (depends on 1, 2, 3)

The decoder of any one of claims 1-3 wherein said memory means directly stores said error patterns and the number of said errors associated with each of said error patterns.

### Claim 9 (depends on 8)

The decoder of claim 8 wherein said memory means comprises a read only memory (ROM), each of said error patterns and said number of errors associated with each of said error patterns being stored as a single word in said ROM, said ROM having an address input receiving said generator output.

### Claim 10

An error correcting system for receiving a plurality of data bits, at least a portion of said data bits being generated in accordance with a predetermined function, said data bits including information bits and coding bits, said system comprising:
decision means for receiving said data bits and for concurrently providing at least first and second decision outputs in accordance with said data bits;
at least first and second decoders receiving said first and second decision outputs, respectively, and concurrently providing first and second decoded outputs, respectively, said first and second decoders detecting the number of errors in said first and second decision outputs, respectively; and
selector means for selecting, for further processing in processing means, one of said first and second decoded outputs associated with the decision output having the fewer number of detected errors.

### Claim 11 (depends on 10)

The error correcting system of claim 10 wherein said decision means ranks said data bits into at least three categories by providing decision bits, at least two of said decision bits thereby identifying each of said data bits as belonging to any one of said at least three categories, the more significant decision bits providing said first decision output, the lesser significant decision bits providing said second decision output.

### Claim 12 (depends on 11)

The error correction system of claim 11 wherein said selector means selects said first decoded output for further processing whenever said number of detected errors for said first and second decision outputs are equal.

### Claim 13 (depends on 12)

The error correction system of claim 12 wherein said first and second decoders comprises:
generator means for processing said respective first and second decision outputs in accordance with said predetermined function to produce first and second generator outputs, respectively;
memory means receiving said first and second generator output for producing first and second error patterns, respectively, said first and second error patterns providing direct indications of which bits of said first and second decision outputs are incorrect; and
correction means for correcting said first and second decision outputs in accordance with said first and second error patterns, respectively, to provide said first and second decoded outputs, respectively.

### Claim 14 (depends on 13)

The error correction system of claim 13 wherein said processing means comprises data output means receiving one of said first and second decoded outputs selected by said selector means, to provide an error corrected output.

### Claim 15

An error correcting decoder for receiving a plurality of data bits, at least a portion of said data bits being generated in accordance with a predetermined function, said data bits including information bits and coding bits, said decoder comprising generator means for processing said data bits in accordance with said predetermined function to produce a generator output;
memory means receiving said generator output for producing an error pattern in response thereto, said error pattern providing a direct indication of which of said information bits are incorrect;
correction means for correcting said information bits in accordance with said error pattern; and
means for disabling said correction means in response to an excessive number of errors in said plurality of data bits.

### Claim 16 (depends on 15)

The decoder according to claim 15, wherein said memory means provides an error count output representing the number of errors indicated by said error pattern, said generator means further comprising an overall parity generator for generating a parity bit based on said plurality of data bits, and wherein said means for disabling is responsive to both said parity bit and said error count output for disabling said correction means when the total number of errors indicated by said error count output and said parity bit exceeds said predetermined number.