JPH0260335A - Encoder and decoder - Google Patents

Abstract

PURPOSE:To decrease the redundancy without reducing the correction capability of an original product code by transmitting the inspection words of only an Rx code word and an Ry code word without transmitting the inspection words of a C1 code word and a C2 code word and decoding with a decoding device. CONSTITUTION:When information arranged to two-dimension in encoded, a C1 encoder 4 encodes a linear code C1 in a C1 encoding direction, and a C2 encoder 5 encodes a linear code C2 in a C2 encoding direction. An Rx encoder 6 encodes the inspection word of the C1 encoder of the linear code in view of an information symbol, and an Ry encoder 7 encodes the inspection word of the C2 code word of the linear code in view of the information symbol of the Ry code word. For the sending of the code word to a communication path, only the inspection word of a code Rx, the inspection of Ry and the information symbol are transmitted. At the receiving side, the transmitted code word is converted to C1 and C2 inspection words by a C1 reproducing device 11, a C2 reproducing device 13, continuously with Rx and Ry decoders 15 and 16, the inspection word on the transmission line, are encoded with C1 and C2 decoders 12 and 14 after the error is corrected. Thus, without reducing the correction capability of a product code, the redundancy degree can be drastically decreased.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to an error correction code encoding and decoding device.

[Prior Art] An example of a conventional error correction code encoding/decoding device called a product code is, for example, a double code.

Double, Peterson & E., J. Weldon, J.R., Error-Correcting Codes, Second Edition, The MIT Press.
1972 P 131-138 (Beast W, Peters
on & E, J., Weldon Jr.'Error
-CorrectingCodes J 2nd E
dition, THE MIT Press, 1972
．． p131138). The outline is two linear codes CI Cc with a relatively small minimum distance.
+ is (n+, ni+, d+) linear code, (where nl is the code length, k is the number of information symbols, d is the minimum distance, the same applies below) 1 and 02, [C2 is (nz, kz , (Iz
) linear code], the product code obtained by combining becomes (n+nz, +kz, d+dz) linear code.

That is, it is possible to obtain a linear code having a minimum distance of d2, which is the product of the minimum distance between two codes.

[Problems to be Solved by the Invention] Since the conventional error correction code encoding/decoding apparatus of this type is configured as described above, it is possible to use a code with a small minimum distance to generate a code with a larger minimum distance. Although very easy to obtain, the redundancy may be too large for the minimum distance, making it inefficient. That is, the linear code C+
, Cz are respectively R, , R2. Since these are given by RI=kl/n+ and Rz=kz/nz, the coding rate of the combined product code is +kz to R-.
/n1n2. That is, for example, R, -R2=0.8
In this case, there were problems such as the low coding rate T-' of 0.64.

This invention was made to solve the above-mentioned problems. First, the check words of the C1 code word and C2 code word are re-encoded by making them correspond to different Rx encoders and R, encoders. , code Rx, without transmitting the check word of code C,,C2,
An error correction code encoding device that makes it possible to greatly reduce redundancy by transmitting only the check word of Ry;
Second, the code sent from the encoding device is received by the decoding device, and the decoding device side performs C1 encoding and C2 encoding again from the information part of the received word, and reproduces the Rx received word and Rz received word. Then, errors in the check words of the C received word and C2 received word are corrected by executing R, decoding, and Ry decoding corresponding to the received word, and then C3 decoding and C2 decoding are performed to correct the product code. An object of the present invention is to obtain a decoding device for an error correction code that constitutes a code with far less redundancy than a product code.

[Means to solve the problem]

The encoding device according to the invention of the first claim is a linear code C.
A C1 encoder encodes 1 in the encoding direction, a C2 encoder encodes a linear code in the 02 encoding direction, and a check word of the 01 codeword of the linear codeword is regarded as an information symbol of the Rx codeword. It is equipped with an Rx encoder for encoding, and a Ry encoder for encoding the check word of the 02 code word of the linear code as an information symbol of the Ry code word.

Further, the decoding device according to the invention of the second claim receives the code word encoded by the encoding device, encodes the information symbol of the received word based on the C5 encoding algorithm, and encodes the information symbol of the received word based on the C5 encoding algorithm.
a C1 regenerator that generates a check word of the C1 code word; a C2 regenerator that encodes information symbols of the received word based on the 02 encoding algorithm to generate a check word of the C2 code word; An R decoder and a Ry decoder that correct errors by decoding check words as information parts of Rx, R, and received words based on an Rx decoding algorithm and a Ry decoding algorithm, respectively, and after decoding, an Rx decoder and a Ry decoder. The C1 decoder and the C2 decoder each decode the C1 received word and the C2 received word using the check words corrected by the decoder.

[For production]

The encoding device in the invention according to the first claim is C1
Only the check words of the R, code word, and Ry code word are transmitted without transmitting the check words of the code word and the C2 code word. Further, the decoding device in the invention according to the second claim converts the received code into C, .
After reproducing with a C2 regenerator, decoding with an Rx, R, decoder,
Finally, the error in the check word is corrected in the 01°C2 decoder to greatly reduce the redundancy of the product code.

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings. 1st
The figure is a hardware block diagram of the encoding device of the present invention, FIG. 2 is an explanatory diagram of the encoding process of FIG. 1, FIG. 3 is a hardware block diagram of the decoding device of the present invention, and FIG. It is an explanatory diagram of the decoding process of the figure.

First, in Figure 1, 1 is the encoding memory and the address /
It is connected to the data/control signal HAS 2 along with the following elements. That is, 3 is an encoding control circuit, 4 is a C1 encoder,
5 is a C2 encoder, 6 is a Ry encoder, and 7 is a Ryy encoder.

Further, FIGS. 2(a) to 2) are diagrams showing the encoding process of the encoding apparatus of FIG. 1. In the figure, 17 is the information symbol of the Xk2 symbol, 18 is the C1 encoding direction, and 19 is the C8
Check word of code word, 20 is C2 encoding direction, 21 is check word of C7 code word, 22 is Rx encoding direction, 23 is code R,
24 is R, the encoding direction, and 25 is the check word of the code Ry.

In FIG. 3, a decoding memory 8 is connected to the address/data/control signal bus 9 along with the following elements as described above. That is, 10 is a decoding control circuit, 11 is C1
12 is a CII encoder, 13 is a C2 regenerator, 14 is a C2 decoder, 15 is an Rx decoder, and 16 is a Ryy encoder.

Next, the operation will be explained. First, as a coding procedure, information symbols of symbols Xk are arranged in a rectangular shape as shown in FIG. 2(a). Then, C1 encoder 4
A check word 19 of the C code word is encoded in the encoding direction 18. This operation is repeated twice to obtain a rectangular arrangement of n+Xkz information symbols as shown in FIG. 2(b).

In addition, the C2 encoder 5 performs encoding in the 02 encoding direction 20 as shown in FIG.
Generates 1. This operation is repeated n1 times and n1Xn2
Obtain the rectangular arrangement of information symbols.

Next, the check word I9 of the 01 code word is regarded as an information symbol of the Rx code and is encoded by the Rx encoder 6 to obtain the check word 23 of the code R.

On the other hand, the check word 21 of the C2 code word is
, in the encoding direction 24 to obtain the check word 25 of the code Ry.

As shown in FIG. 2(f), the code word is transmitted to the communication channel by combining the information part of the xkz symbol and the check word 23 of the code Rx.
Send only check word 25 of Ry, check word 1 of C8 code word
9. Check word 21 of the C2 code word is not transmitted.

The above operation is performed by commands from the encoding control circuit 3.
This is done via the data/control signal HAS2.

On the receiving side, the received word corresponding to FIG. 2(f) is reproduced in the decoding memory 8.

FIG. 4 is a diagram showing the decoding process of the decoding device of FIG. 3. In the figure, 26 is a decoding error that occurred on the transmission path;
27 is the C1 encoding direction, 28 is the C1 check word regenerated by the C0 regenerator, 29 is the pseudo error newly occurring on the transmission path in the CII check word that has been subtracted by an error on the transmission path, and 30 is the result of Rx decoding. Corrected C9 check word, 31 is CI decoding correction error correctly corrected by CI decoding, 3
2 is a C1 decoding addition error correction error newly added by CI decoding due to an error exceeding the correction ability, and 33 is a C1 decoding addition error correction error.
2 C2 encoding direction by the regenerator, 34 is a pseudo error of C2 check word caused by C1 decoding caused by C2 decoding, 35 is error corrected by Ry decoding, 36 is C2
This is an error corrected by decoding.

On the decoding side, as shown in FIG.
The C8 test word is reproduced. At this time, a transmission path pseudo error 29 occurs in the C1 check word corresponding to a location where an error occurs on the transmission path. The Rx decoder 15 decodes the Rx received word using the reproduced C1 check word 28 to correct errors. 30 shows the corrected CII search word. C decoding is executed using the correctly reproduced C9 test word 30. 31 is a C1 decoding correction error corrected by C1 decoding, and 32 is a C8 newly added due to error correction.
This is a decoding addition error correction error.

Next, as shown in FIG. 4(d), the 02 regenerator 13 encodes in the 02 encoding direction 33 to reproduce the C2 check word. 34 is a pseudo error in the C2 check word caused by the CI decoding error caused by the C5 decoding error. These pseudo errors are correctly corrected by the R9 decoder 16 as shown in FIG. 4(e). 35 is Ry decoding and correction.

In addition, as shown in (f) of the same figure, the correctly reproduced C2
Decoding is performed by the C2 decoder 14 based on the check word, and C
2. Correct the decoding correction error.

The above configuration is, for example, n+]'(1=bl-, nz
kz-s, then C1 code and C2 code are BCH codes with minimum distance d, d2, and code Rx has minimum distance d2.
, CF (2b1) Up-Daw Solomon (Reed-
5olomon) code to the code R, the minimum distance dd2
, Reed-So I omon on CF (2b2)
It can be configured using codes.

〔Effect of the invention〕

As described above, according to the invention according to the first claim, the transmission information from the encoding device transmits only the check words of the codes Rx and Ry and the information symbols of k + X k 2, and the second In the decoding device of the claimed invention, the transmitted code word is converted into C, C, check words by the CI and C2 regenerators, and then the check words on the transmission path are error-corrected by the Rx and Ry decoders. After that, the code is encoded by the C, , C2 decoder, which has the effect of significantly reducing redundancy without reducing the correction ability of the original product code.

[Brief explanation of the drawing]

FIG. 1 is a /S-ware block diagram of the encoding device according to the present invention, and FIG. 2 is an explanatory diagram of the encoding process according to the present invention.
FIG. 3 is a hardware block diagram of a decoding device according to the present invention, and FIG. 4 is an explanatory diagram of the decoding process according to the present invention. In the figure, 1 is an encoding memory, 4 is a C1 encoder, 5 is a C2 encoder, 6 is an R encoder, 7 is a Ry encoder, 11 is a c regenerator, 12 is a C1 decoder, 13 is a C2 encoder Regenerator, 1
4 is a C2 decoder, 15 is an Rx decoder, and 16 is an R decoder. In addition, in the figures, the same reference numerals indicate the same or equivalent parts. Patent applicant Mitsubishi Electric Corporation E-1 (bl (c) (dl el Procedural amendment (voluntary) (f) 2. Invention name encoding and decoding device 3. Representative of the person making the amendment Moriya Shiki 4. Agent Address Postal Code 105 1-4-10 Nishi-Shinbashi, Minato-ku, Tokyo 6. Contents of Amendment (1) The scope of claims is amended as shown in the attached sheet. (2) Page 2, line 16 of the specification On the 19th line of the same page, the phrase [e.g. double...chord] is replaced with "e.g. W.W. Beaterson and Yi Liu.
Corrected with ``Error-Correcting Course'' by Welton G.R. (3) On page 4, line 16 of the specification, "R2 received word" is corrected to "Ry received word." (4) In the fifth line of page 5 of the specification, the statement "1i-type code c1 in the encoding direction" is corrected to "linear code c1 in the 01 encoding direction". (5) In the 6th line of page 5 of the specification, [linear code in 02 encoding direction] is replaced with "linear code c2 in 02 encoding direction".
and correct it. (6) From line 9 on page 9 of the specification to line 10 on the same page, the phrase "decoding error that occurred" is corrected to "error that occurred." (7) On page 9, line 13 of the specification, the phrase "transmission path pseudo error" is corrected to "pseudo error." (8) On page 9, line 15 of the specification, the phrase "corrected C1 decoding correction error" is amended to read "corrected error." (9) In the 17th line of page 9 of the specification, the phrase "added C1 decoding additional miscorrection error" is corrected to "added miscorrection error." (10) On page 9, line 19 of the specification, [triggered C2
The phrase "in decoding" is corrected to "in triggered C2 encoding." (11) The phrase "pseudo error" on page 9, line 20 of the specification is corrected to "pseudo error." (12) "Pseudo error on transmission line" on page 10, line 6 of the specification
This is corrected as a "pseudo error". (13) From line 11 on page 10 of the specification to line 12 on the same page: “
``Corrected C1 decoding correction error'' is corrected to ``corrected error''. (14) In the 13th line of page 10 of the specification, "added C1 decoding addition error correction error" is corrected to "added error correction error." (15) On page 10, line 17 of the specification, the phrase ``pseudo error of C2 check word due to rc and decoding equipment'' is corrected to ``pseudo error due to C3 decoding error''. (16) The phrase "pseudo error" on page 1, line 18 of the specification is corrected to "pseudo error." (17) On page 10, line 20 of the specification, "decoding correction error" is corrected to "error corrected by decoding." (18) “c2 decoding correction error” on page 11, line 3 of the specification
The statement has been corrected to "C2 decoding error." (19) Correct Figure 4(a) as shown in the attached sheet. 7. List of attached documents (1) One document stating the amended scope of claims (2) One or more documents stating the amended figure 4(a) 1) In an encoding device that encodes information arranged two-dimensionally, 11&C and C1 encode in the encoding direction.
encoder and C2 encoding in the direction 211 to C2 encoding
an encoder; R; encodes a check word of the 01 code word of the linear code as an information symbol of the R8 code word; an encoder; 1. An encoding device comprising: an encoder; and an encoder. (2) In a decoding device that decodes encoded information obtained by encoding information symbols arranged two-dimensionally, the information symbols of the received word that received the encoded code word are encoded based on the 01 encoding algorithm. a C2 regenerator that encodes information symbols of the received word based on the 02 encoding algorithm to generate a check word of the C2 codeword; A Ry decoder and an R decoder each decode the reproduced check word as an information part of the received word based on the R decoding algorithm and the R decoding algorithm, and the R decoder. 1. A decoding device comprising a C1 decoder and a C2 decoder that decode a C3 received word and a C2 received word, respectively, using check words corrected by the decoder and the R9 decoder.

Claims (2)

[Claims] (1) In an encoding device that encodes information arranged two-dimensionally, a C_1 encoder encodes a linear code C_1 of the information in a C_1 encoding direction, and a linear code C_1 of the information
a C_2 encoder that encodes _2 in a C_2 encoding direction;
an R_x encoder that views and encodes the check word of the C_1 code word of the linear code as an information symbol of the R_x code word; and an R_y encoder that views the check word of the C_2 code word of the linear code as the information symbol of the R_y code word and encodes it. An encoding device comprising: an encoder. (2) In a decoding device that decodes encoded information obtained by encoding information symbols arranged two-dimensionally, the information symbol of the received word that received the encoded code word is C_1.
A C_1 regenerator that encodes based on an encoding algorithm to generate a check word of a C_1 code word; and a C_2 regenerator that encodes information symbols of the received word based on a C_2 encoding algorithm to generate a check word of a C_2 code word. and the check words regenerated by the regenerator are R_x and R_y, respectively.
R_x decoding algorithm, R_ as the information part of the received word
R to decode and correct errors based on the y decoding algorithm
_x decoder and R_y decoder, and a C_1 decoder and a C_2 decoder that decode the C_1 received word and the C_2 received word, respectively, using the check words corrected by the R_x decoder and the R_y decoder. Characteristic decoding device.