Browse Prior Art Database

A Class of Error Correcting Codes with Simple Encoders and Decoders

IP.com Disclosure Number: IPCOM000093029D
Original Publication Date: 1967-Apr-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 5 page(s) / 83K

Publishing Venue

IBM

Related People

Eggenberger, JS: AUTHOR

Abstract

This class of codes can be decoded and corrected by a single layer of threshold devices. Each decoded and corrected binary digit is generated by comparing the weighted sum, in the field of real numbers, of the code digits with a threshold.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 28% of the total text.

Page 1 of 5

A Class of Error Correcting Codes with Simple Encoders and Decoders

This class of codes can be decoded and corrected by a single layer of threshold devices. Each decoded and corrected binary digit is generated by comparing the weighted sum, in the field of real numbers, of the code digits with a threshold.

Conventional error-correcting codes are, for the most part, group codes. Group codes have a fairly simply described structure and can be encoded by linear, modulo-2 operations. They also achieve a high degree of error-correcting ability for their redundancy. However, the decoding and correcting circuitry must be nonlinear and can be highly complex. The decoder complexity increases with increasing block length. A long block length is desirable since it results in more error correction for a given redundancy.

The approach used in conventional error-correcting codes is to design a code having maximum error-correcting ability, then to design as simple a decoder as possible which can realize this error-correcting ability. The approach used to design the codes in this article is to specify a simple decoding and correcting structure. Then the code, which can be decoded by this structure with maximum error-correction, is determined.

The particular decoding structure considered consists of a single layer of threshold devices. Thus, to determine the corrected value for each decoded digit, a weighted sum of the code digits is first generated for each decoded digit. These weighted sums are then compared with thresholds. The binary digits of the decoded word are assigned depending on whether their corresponding weighted sum is greater or less than the corresponding threshold. The codes and decoder can also be used for error-detection by incorporation of a dead zone around the threshold. If the weighted sum is greater than the upper limit of the dead zone, one binary variable is assigned. If the weighted sum is less than the lower limit of the dead zone, the other binary variable is assigned. A weighted sum falling within the dead zone signifies an uncorrectable error. This decoding structure requires only linear adders, resistive, magnetic core, or otherwise, and threshold comparators.

Thus, a parallel decoding structure for an (n, k) code, that is, an encoding of k binary variables into n binary variables, consists of k threshold devices with n inputs each. The decoding structure can be described by an n-row x k-column weight matrix. In this, the element in the ith row and the jth column is the weight of the ith code variable in the threshold device generating the jth decoded variable, and a set of k thresholds. The optimum choice of threshold is such that a random set of n binary digits into the decoder, with either digit equiprobable, is equally likely to produce either output. If the binary variables are +/-1, this implies that all thresholds in the decoding structure should be zero and the structure can be described by the n x k weight...