Error-correction encoding and decoding system

Details Error-correction encoding and decoding system Error-correction encoding and decoding system

1991-10-10

1994-12-06

Beausoliel, Jr., Robert W.

Excavating

G06F 1110, H03M 1300

Patent

active

053717503

DESCRIPTION:

BRIEF SUMMARY
BACKGROUND OF THE INVENTION

1. Field of the Invention
The present invention relates to an encoder and a decoder for realizing an error-correction encoding and decoding system for processing an error-correcting code, the code being made by superimposing error-correcting codes respectively generated from a couple of pieces of information and a decoding system utilizing such a decoder.
2. Discussion of Related Art
FIG. 1 shows an example of a code format utilizing a product code, i.e., first information I.sub.p, which is required to be highly reliable, and second information I.sub.s, which is not required to have such a high reliability. See Peterson et al., Error-Correcting Codes p. 131-136 (MIT Press, 1972). As shown in FIG. 1, first information I.sub.p of k.sub.1 .times.k.sub.2 digits is encoded by a product code. Namely, this first information I.sub.p is encoded to a product code, having as a partial code, a linear code C.sub.11 having a code word length n.sub.11, information code length k.sub.1, and minimum code length d.sub.11 (hereinafter a linear code of code word length N, information code length K, and minimum code length D will be called a (N, K, D) linear code C). First information I.sub.p also has (n.sub.2, k.sub.2, d.sub.2) linear code C.sub.2 as a partial code. The composite minimum distance is d.sub.11 .multidot.d.sub.2.
On the other hand, second information I.sub.s of r.times.k.sub.x digits (r<n.sub.11 -k.sub.1) is encoded to a block code, e.g., a (n.sub.2, k.sub.x, D) linear code C.sub.3 on a Galois field GF(2.sup.r). In this case, the product code and linear code C.sub.3 are not superimposed with each other and are transmitted separately.
FIG. 2 shows an example of a code format for encoding first information I.sub.p and second information I.sub.s using a superimposed code, introduced, for example, by M. Kasahara, et al., "New Classes of Binary Codes Constructed on the Basis of Concatenated Codes and Product Codes," IEEE Transaction on Information Theory, Vol, IT -22, No. 4, p. 462-468 (July 1976). In this case, first information I.sub.p is encoded to a product code of the compound minimum distance d.sub.1 .multidot.d.sub.2 by using the partial codes (n.sub.1, k.sub.1, d.sub.1) linear code C.sub.1 and (n.sub.2, k.sub.2, d.sub.2) linear code C.sub.2. Second information I.sub.s of (n.sub.1 -k.sub.1).times.(n.sub.2 -(d.sub.1 .multidot.d.sub.2 -1)) digits is encoded by an RS (Reed-Solomon) code on GF(2.sup.r) of the minimum distance d.sub.1 .multidot.d.sub.2 -1. Here, r=n.sub.1 -k.sub.1 and a code word C.sub.s of the RS code is superimposed on a check field C.sub.h (hatched portion in FIG. 2) of the product code.
Next, an encoding operation will be explained. First information I.sub.p is encoded to a product code, while second information I.sub.s is encoded to an (n.sub.2, n.sub.2 -d.sub.1 .multidot.d.sub.2 +1, d.sub.1 .multidot.d.sub.2 -1) RS code on GF(2.sup.r ). A code word of the product code is C.sub.p and a code word of the RS code is C.sub.s. Code word C.sub.s is superimposed on code check field C.sub.h (C.sub.h is assumed to include a check field of linear code C.sub.1 and an internal check field for this check field). After such superimposing the resulting code word C.sub.y is transmitted to a transmission line.
Here, the i-th symbol R.sub.i of code word C.sub.s is expressed as R.sub.i =(R.sub.i1, R.sub.i2, . . . , R.sub.ir), and M.sub.i is defined as follows: ##EQU1##
.sym. means modulo-2 sum and H.sub.i designates a symbol of check field C.sub.h. Moreover, F.sub.i is defined as follows:
I.sub.i is an information symbol of linear code C.sub.1. Therefore, code word C.sub.y may be expressed as a vector (F.sub.1, F.sub.2 , . . . , F.sub.q) where q=n.sub.2.
In addition, the article in the IEEE journal, cited above, provides the following theorem: after the superimposing can correct errors when the minimum distance D.sub.1 satisfies the relationship t=[(D.sub.1 -1)/2.
Next, a decoding operation will be explained. Here, re-encoding a received information symbol series is called "separat

REFERENCES:
patent: 4665537 (1987-05-01), Moriyama
patent: 5070503 (1991-12-01), Shikakura
Kasahara et al., "New Classes of Binary Codes Constructed on the Basis of Concatenated Codes and Product Codes" IEEE Trans. on Information Theory, vol. IT-22, No. 4, Jul. 1976.

Affiliated with

Also associated with

Rating

Error-correction encoding and decoding system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Error-correction encoding and decoding system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error-correction encoding and decoding system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-220096