JPH07114372B2 - Error correction code decoding method - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a method for decoding an error correction code such as a product code and a cross interleave code.

[Outline of Invention]

The present invention relates to a first series and a second series which are arranged in different directions of a two-dimensional array of a plurality of symbols of digital data.
In the decoding method of the error correction code in which the first error correction code and the second error correction code are coded in each of the sequences, the error between the predetermined first sequence and the predetermined second sequence is increased. The two-dimensional array is set from the set series to the adjacent series such that the series with the smaller number is set as the series to be corrected first, and then the first series and the second series are alternately processed. By sequentially performing the correction processing of the series of, the error correction capability is improved within a predetermined calculation time, and in addition, the burst error can be effectively corrected.

[Conventional technology]

When storing digital data on a magneto-optical disk,
Product codes are used to correct errors that occur when writing or reading data. The product code encodes an error correction code for each column and each row of a two-dimensional array (matrix block) of digital data, and a linear code is used as the error correction code.

A conventional product code decoding method is disclosed in, for example, Japanese Patent Laid-Open No.
As shown in the publication, C1 decoding that performs the error correction code C1 in the column direction for all sequences of the code C1 and C2 decoding that performs the error correction code C2 in the row direction for all sequences of the code C2 and Are alternated.

[Problems to be solved by the invention]

When correcting a burst error that occurs when data is transmitted in the diagonal direction (diagonal direction) of the matrix block of the product code, the conventional decoding method is decoding of code C1 and code C1.
There was a problem that the error symbol could not be corrected unless the number of times each C2 decoding was repeated was increased. Therefore, when the operation time allocated for decoding one matrix block of the product code is not sufficiently long, there is a problem that uncorrected error symbols remain.

The above-mentioned problem occurs not only in the product code but also in the cross interleave code. The cross-interleaved code encodes the first error correction code and the second error correction code for each series of two diagonally arranged different two-dimensional arrays of digital data, and the column direction is the data transmission direction. It is a thing. As in the conventional method, the first error correction code is decoded for all code sequences, and then the second error correction code is decoded.
The decoding method in which the error correction code is decoded for all code sequences cannot effectively correct the burst error.

Therefore, an object of the present invention is to provide a decoding method of an error correction code capable of effectively correcting a burst error.

[Means for solving problems]

According to the present invention, each block of a first series C1 ₁ , C1 ₂ , ... C1 _N in which one block aligned in the first direction of a two-dimensional array of a plurality of symbols of digital data is composed of a plurality of symbols The first error correction code C1 is encoded into
The first error correction code C2 is coded for each block of the second sequence C2 ₁ , C2 ₂ , ... C2 _M in which one block aligned in the second direction of the dimensional array is composed of a plurality of symbols. In the decoding method of the error correction code, the predetermined first sequence
A step of setting a series having a smaller error between C1 _n and a predetermined second series C2 _m as a series for performing the correction process first, and the first series and the second series in units of one block A method for decoding an error correction code, comprising the steps of sequentially performing correction processing of a series of a two-dimensional array from a set series to an adjacent series so that the series are alternately processed.

[Action]

In the case of a product code in which the error correction code C1 is encoded in the column direction of a two-dimensional array (matris block) of a plurality of symbols of digital data, and the error correction code C2 is encoded in the row direction, in the column direction Column block C1 ₁ , which is a sequence of
C1 ₂ , ... C1 _N and row block C2 ₁ , C
2 ₂ , ..., C 2 _M are corrected alternately for each block. When data is transmitted in a diagonal direction of a matrix block, one column block or one row block includes an error correctable number, for example, two or more error symbols, which is more than one error symbol, due to a burst error. An error pattern occurs. In the case of such an error pattern, the number of error symbols is small, and the error processing is performed by alternately processing the column block and the row block for each adjacent block from the column block or the row block that can perform error correction. Is corrected. Therefore, when performing the decoding process within a predetermined time,
The error correction capability can be substantially increased.

〔Example〕

An embodiment in which the present invention is applied to a product code will be described below with reference to the drawings. FIG. 1 shows a decoding device for carrying out the decoding method according to the present invention.

In FIG. 1, digital data and check symbols forming a matrix block of product codes are stored in a memory (RAM) designated by 1. The data stored in the memory 1 is one sector of data reproduced from a magneto-optical disk (not shown). The write address and the read address of the memory 1 are generated by the memory address control circuit 2. The data of one column block or row block read from the memory 1 is supplied to the input / output control circuit 3.

The input / output control circuit 3 is connected to a decoder (C1 decoder) 4 for the error correction code C1 in the column direction and a decoder 5 (C2 decoder) 5 for the error correction code C2 in the row direction. The input / output control circuit 3 is controlled by a control signal generated from the address control circuit 2. When the address control circuit 2 generates address data for reading the column block data to the memory 1, the memory 1 and the C1 decoder 4 are connected, and the read column block data is C1 decoded. Then, the correction process is performed on the column block and the corrected column block data is written to the memory 1. On the other hand, when the address control circuit 2 generates address data for reading the row block data from the memory 1, the memory 1 and the C2 decoder 5 are connected,
The read row block data is supplied to the C2 decoder 5, correction processing is performed on this row block, and the corrected row block data is written to the memory 1.

The address control circuit 2 generates address data such that the data of the column block and the data of the row block are alternately read from the memory 1 from the column block or the row block where the decoding is started. A start block setting circuit 6 is provided to set a start block for starting decoding. In this embodiment, one of the predetermined column block C1 _n or the predetermined row block C2 _m is set as the start block. As will be described later, the start block setting circuit 6 sets C1 _n as the start block when the column block C1 _n can be corrected, and starts C2 _m when the column block C1 _n cannot be corrected. Set to block. Therefore, the determination signal from the C1 decoder 4 indicating whether correction is possible is supplied to the start block setting circuit 6.

FIG. 2 shows an example of the structure of a product code to which the present invention can be applied. As shown in FIG. 2, an encoding unit is formed by a matrix block composed of (M · N) symbols arranged in a matrix of M rows and N rows. The error correction code is encoded for each column block and each row block of [(MP) × (NQ)] digital data symbols (for example, one symbol is 1 byte). In the case of a storage device using a magneto-optical disk, (M
-P = N-Q = 23), and one matrix block has a size of 529 bytes corresponding to one sector. Of these 529 bytes, 512 bytes are digital data and the other 17 bytes are additional data such as address, identification code and CRC code.

Each of the N column blocks C1 ₁ , C1 ₂ , ..., C1 _N is a code sequence of the error correction code C1 and includes P check symbols. Similarly, M row blocks C2 ₁ , C2 ₂ , ...
Each of C2 _M is a code sequence of the error correction code C2,
It contains Q check symbols. That is, the Q column blocks including the column block C1 _N are obtained by encoding the code C1 on the check symbol of the code C2, and the P row blocks including the row block C2 _M are checked by the code C1. The symbol is the code C2 encoded. Linear codes are usually used as the error correction codes C1 and C2. For example, a Reed-Solomon code capable of correcting one symbol error is used as the error correction codes C1 and C2,
Each of the column block and the row block includes (P = Q = 2) check symbols. Further, since the check symbols in the portion where the P row blocks and the Q column blocks overlap each other are linear codes, the check symbols are the same between the row blocks and the column blocks.

As shown by the broken line in FIG. 2, data is transmitted in the order of symbols located in the diagonal direction (diagonal direction) of the matrix block. Transmitting data in a diagonal direction different from the direction of the series of the error correction codes C1 and C2 disperses burst errors that occur during transmission into random errors, and error correction becomes impossible with the error correction codes C1 and C2. This is to avoid that.

The C1 decoder 4 and the C2 decoder 5 decode the product code shown in FIG. The memory 1 stores all the data of the matrix block reproduced from the magneto-optical disk, and the memory 1 is stored for each column block or row block forming a code sequence.
The data is read from and the Reed-Solomon code is decoded. When the column blocks C1 ₁ , C1 ₂ , ..., C1 _{N of} digital data are read from the memory 1, the memory 1 and the C1 decoder 4 are connected by the input / output control circuit 3. Similarly, when the row blocks C2 ₁ , C2 ₂ , ..., C2 _{M of} digital data are read from the memory 1, the input / output control circuit 3 connects the memory 1 and the C2 decoder 5 to each other.

In the decoding process of the Reed-Solomon code, a step of obtaining two syndromes S ₀ and S ₁ by multiplying the parity check matrix and the symbol of each block, and this syndrome S ₀
And checking the magnitude of the error from S ₁ .
When there is a 1-symbol error, the error is corrected.

Conventionally, C1 decoding for performing error correction on all column blocks C1 ₁ , C1 ₂ , ..., C1 _N and all row blocks C2 ₁ ,
Correction processing is performed by a method of alternately repeating C2 decoding for performing error correction for C2 ₂ , ..., C2 _M. The present invention is a method which has a correction capability equivalent to that of a conventional correction process and can further shorten the compound time, and corrects the code sequence of the column block and the code sequence of the row block alternately for each block. Is. FIG. 3 is a flow chart of a correction processing method according to an embodiment of the present invention. In FIG. 3, Y represents positive and N represents negative.

One of the predetermined column block C1 _n and the predetermined row block C2 _m is the decoding start sequence. For example, (C1 _n = C1 ₁ ) (C2 _m
= C2 ₁ ) and the symbols of these start blocks are read from the memory 1 (step).

Next, it is checked from the syndrome whether or not one of the decoding start sequences, for example, the column block C1 _n can be corrected (step). If there is no error symbol or if there is an error of one symbol, the process proceeds to the correction process of the column block C1 _n (step). The correction process means a reversal process of the Reed-Solomon code, and does not mean only when an error can be corrected.

Next, the row block C2 _m is corrected (step). Whether or not a correction end signal has arrived is checked in a step, and if so, the correction process ends. In this step and the correction process of the step, the column block C1 _n and the row block C2 _m are read from the memory 1 first.

In step, when the correction end signal has not arrived, the block number (n and m) is incremented by (+1) (step), and the process of step is repeated. Therefore, the code C1 in the order of [C1 _n → C2 _m → C1 _{n + 1} → C2 _{m + 1}
And the sequence of code C2 are alternately processed for each block.

If correction cannot be performed because the column block C1 _n , which is one decoding start sequence, contains two or more error symbols, the row block C2 that is the other decoding start sequence
Correction processing of _m is performed (step). When the correction process of C2 _m is completed, the block number m is incremented by (+1) (step), and the process returns to the above step (correction process of the column block C1 _n ). Therefore, [C2 _m → C1 _n → C2 _{m + 1} → C1 _{n + 1}
..], the sequence of code C1 and the sequence of code C2 are alternately processed for each block.

The error correction according to the present invention, in which the sequence of the code C1 and the sequence of the code C2 are alternately processed for each block, is counterproductive to the error pattern correction as shown in FIG.

In FIG. 4, for simplification, the matrix block shows the product code of 7 rows and 7 columns, and the symbol shown by x shows the error symbol. As general correction processing, all decoding of column blocks (C1 decoding) that is a sequence of code C1 that can correct one symbol error and all row blocks that are sequences of code C2 that can correct one symbol error Decoding (C2 decoding) and (C1 decoding → C2 decoding) or (C2 decoding →
In any case of C1 decoding), the six error symbols surrounded by the broken line are not corrected.

However, as described above, starting from the correction of the _first row block C2 ₁ , the C1 series and the C2 series are arranged in the order of (C2 ₁ → C1 ₁ → C2 ₂ ... C2 ₇ → C1 ₇ ). By performing correction processing alternately, all error symbols can be corrected. That is, more error symbols can be corrected with substantially the same number of correction steps, and the limited correction processing time can be effectively used. Fourth
The error pattern shown in the figure is likely to be caused by a burst error when transmitting data in the diagonal direction of the matrix block, and the correction process of this embodiment is very effective for correcting the burst error.

Of course, the present invention can be applied to not only the product code but also the code for performing the error correction code in the diagonal direction of the matrix block. In addition, as the error correction code, a code other than the Reed-Solomon code can be used. For example, when one symbol has 1 bit, a BCH code can be used.

〔The invention's effect〕

According to the present invention, due to a burst error during transmission, 2
For both error correction code sequences C1 and C2, the error pattern (the error pattern that can be finally corrected by repeating C1 decoding and C2 decoding several times) with many sequences containing multiple error symbols When decoding, the number of steps can be reduced and the decoding time can be shortened as compared with the conventional decoding method.

[Brief description of drawings]

FIG. 1 is a block diagram of an embodiment of the present invention, FIG. 2 is a schematic diagram used to explain a code configuration of an embodiment of the present invention, and FIGS. 3 and 4 are of an embodiment of the present invention. 9A and 9B are a flowchart and a schematic diagram used for explaining a correction process. Description of main symbols in the drawings 1: Memory, 2: Address control circuit, 3: Input / output control circuit, 4: C1 decoder, 5: C2 decoder.

Claims (1)

[Claims] 1. A first error correction for each of the blocks of a first series in which one block aligned in the first direction when a plurality of symbols of digital data are two-dimensionally arrayed is composed of a plurality of the symbols. The code is encoded, and the second error correction code is encoded for each of the blocks of the second sequence in which one block aligned in the second direction of the two-dimensional array is composed of a plurality of the symbols. In the decoding method of the error correction code, the step of setting a series having a smaller error between the predetermined first series and the predetermined second series as a series for performing correction processing first, In order that the first series and the second series are alternately processed in the unit of one block, the correction processing of the series of the two-dimensional array is sequentially performed from the set series to the adjacent series. The method of decoding error correction codes, characterized in that comprising a flop.