JP3512690B2 - Code synchronization circuit - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a BCH (Bose C)
The present invention relates to a code synchronization circuit used for an error correction system that uses a cyclic code such as a Haudhuri Hocqenghem code and establishes code synchronization by codeword syndrome. In particular, the present invention relates to a code synchronization circuit that can reduce the time required for code synchronization.

[0002]

2. Description of the Related Art An example of code synchronization using the above-mentioned code word syndrome is disclosed in Japanese Patent Application Laid-Open No. 1-274248. However, the present invention aims at shortening the time required for code synchronization. The prerequisite code synchronization circuit itself will be described in detail below.

FIG. 5 is a block diagram illustrating a schematic configuration of a code synchronization circuit which is a premise of the present invention. As shown in the figure, a syndrome calculation circuit 15 is provided in the code synchronization circuit, and the syndrome calculation circuit 15 generally derives a syndrome polynomial by a division circuit of a received data sequence and a generator polynomial.

FIG. 6 is a block diagram showing a schematic configuration of the syndrome calculation circuit 15 of FIG. As shown in this figure,
The syndrome calculation circuit 15 generates the reception polynomial R (x) after all the n bits of the reception data sequence have been input.
Coefficients (S ₀ , S ₁ ,..., _Sa-3 , _Sa-2 , _Sa-1 ) of the syndrome polynomial, which is the remainder multiplied by (x)
Is output.

Therefore, the syndrome cannot be calculated until the input of all the n-bit code words is completed.
The calculation of the next syndrome is started after the previous syndrome calculation is completed. That is, in the zero detection circuit 11, an n-bit code word break (S ₀ = S ₁ = ... = _Sa-3 = _Sa-2 = S) from a continuous received data sequence.
_a-1 = 0) requires a maximum of n syndrome calculations.

FIG. 7 is a view for explaining a code synchronization sequence of the syndrome calculation circuit 15 of FIG. As shown in the figure, the conventional syndrome calculation is a serial process for every n clocks, so that a maximum of n × (n + 1) −1 clocks is required for n times of syndrome calculations.

[0007] As shown in FIG. 5, by adding an (n + 1) -bit counter 18 to an n-bit counter 17 and performing parallel processing, the time required for code synchronization can be reduced.

[0008]

However, in the above code synchronization circuit, when the time of code synchronization is reduced,
It is sufficient to increase the number of parallel processes, but this has a problem that the circuit scale of the parallel processes increases. Accordingly, the present invention has been made in view of the above problems, without increasing the circuit scale of parallel processing.
It is an object of the present invention to provide a code synchronization circuit capable of shortening the code synchronization time.

[0009]

According to the present invention, there is provided a code synchronization circuit for establishing code synchronization of a code word using a cyclic code in which a received data sequence is multiplied by a generator polynomial. A zero detection circuit that determines code divisions from a position where the coefficient of the remaining syndrome polynomial becomes zero to establish code synchronization, and a syndrome polynomial relating to a reception polynomial one clock after the reception polynomial at the instant of clock t. A coefficient is sequentially obtained for each bit input of the data sequence ,
E Bei a syndrome sequential calculation circuit outputs the zero detection circuit, the syndrome sequential calculation circuit, the received data
N clocks that provide n clock delays for column bit inputs
A lock delay circuit, and n passing through the clock delay circuit
Received data input before the clock,
Enter the highest order coefficient of the polynomial, and enter
A plurality of coefficient calculation circuits for forming coefficients, and
Each of the coefficient calculation circuits is a top of the syndrome polynomial.
A first multiplier for multiplying the order coefficient by a first known coefficient;
A second known coefficient added to the received data input before the clock.
And a second multiplier for multiplying each of the coefficient circuit circuits
A first adder for adding the output of the first multiplier to
Adding the output of the second multiplier to the output of the first adder
A second adder, and the output of the second adder for one clock.
And a delay unit for delaying the output of the
Connected to the input of the coefficient calculation circuit
A code synchronization circuit is provided.

By this means, every time the received data is input,
The next syndrome processing is performed and the reception
Calculate coefficients of syndrome polynomials related to terms
Will, without increasing the circuit scale of the parallel processing, it is capable ing to shorten the code synchronization time.

Preferably, one clock of the coefficient calculation circuit is provided.
Each of the syndrome polynomials for the receiving polynomial after
The coefficient S _{i, t−1} is the highest order of the syndrome polynomial.
The coefficient S _{a−1, t} and the output R of the n-clock delay circuit
_{t + (n−1)} , first known coefficient B _i , second known coefficient
When _{C i, S i, t-} 1 = S a-1, t · C i + S i-1, t + R
_{t + (n−1)} · B _i (i is an integer of 1 or more and a−1 or less) S _{0, t−1} = S _{a−1, t} · C ₀ + R _t−1 + R
It is represented by a recurrence formula of _{t + (n−1)} · B ₀ (i is 0) .

Conventionally, the input of all n-bit codewords
Syndrome cannot be calculated until
The large required time was n × (n + 1) clocks.
Means for performing the syndrome processing every time the received data is input.
And the maximum required time is less than 2n clocks.
Not just increase the size of the parallel processing circuit.
And the calculation time can be greatly reduced.

[0013]

Preferably, an n clock counter is further provided, and the n clock counter is provided for n clock periods from the time of initialization when the syndrome sequential calculation circuit cannot be used.
The detection of the zero detection circuit is excluded. By this means, it is possible to remove an error that occurs when the coefficients of the syndrome polynomial become indefinite at the time of initialization.

[0015] Preferably, the cyclic code is a BCH code. By this means, application to the BCH code is expanded.
Preferably, the zero detection circuit is replaced by a syndrome determination circuit, and the syndrome determination circuit obtains in advance each coefficient of a syndrome polynomial of a continuous codeword that is inverted and transmitted at a specific position in advance, and calculates the syndrome successively. The syndrome sequence calculated by the circuit is compared with the coefficient, and a matching position is determined as a code word break to establish synchronization.

By this means, for a syndrome polynomial of a continuous code word which is transmitted at a specific position and inverted in advance,
It is possible to determine the establishment of synchronization.

[0017]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing a schematic configuration of a code synchronization circuit according to the present invention. Note that the code length of a codeword used in the circuit of the present invention is defined as n (n is a positive integer), and the degree of a generator polynomial for generating the codeword is defined as a (a is a positive integer).

In addition, operations such as addition and multiplication in the present invention are as follows.
All operations are performed on GF (2) (GaloisField) fields, and the adder used in the circuit of the present invention can be realized by a two-input exclusive OR circuit, and the multiplier can be realized by a two-input AND circuit. it can. As shown in the figure, the code synchronization circuit according to the present invention is provided with a syndrome successive calculation circuit 10, which calculates a syndrome corresponding to a received data sequence input for each clock and outputs a bit. Outputs the coefficients of the syndrome polynomial in.

Further, the code synchronizing circuit is provided with an n-clock counter 13. The clock counter 13 has an indefinite output of the syndrome sequential calculation circuit 10 and cannot be used. Is output. A zero detection circuit 11 is connected to the syndrome sequential calculation circuit 10, and the zero detection circuit 11 detects a code word division where all the coefficients of the syndrome polynomial become zero except for a mask period by the clock counter 13, and determines the position of the code word. Output.

A frame synchronization protection circuit 12 is connected to the zero detection circuit 11. The frame synchronization protection circuit 12 protects the output of the zero detection circuit 11 from forward protection and rear protection in consideration of errors on the transmission path. And outputs a code synchronization signal. Incidentally, as good as the known above code synchronization forward protection, there is discontinuity mismatch detection, for example, the protection stage X (X is a positive integer) when the, once established synchronization position, X consecutive Syndrome The code synchronization error is prevented by starting the code synchronization re-establishment process only when is different from zero and ignoring other syndrome errors.

As a well-known code-synchronous backward protection, there is a continuous coincidence detection.
If (Y is a positive integer), the synchronization is established only when the syndrome has become zero consecutively Y times at the synchronization position where the detection of the syndrome zero has been successful, otherwise the code synchronization establishment process is continued. By doing so, a code synchronization error is prevented.

FIG. 2 shows the syndrome sequential calculation circuit 1 of FIG.
FIG. 2 is a diagram illustrating a schematic configuration of a zero. As shown in the figure, the syndrome sequential calculation circuit 10 is composed of a coefficient calculation circuits 21
And an n-clock delay circuit 22. The n clock delay circuit 22 delays the input signal by n clocks. The a coefficient calculation circuits 21 calculate the highest coefficient S _a-1 of the syndrome and each coefficient B _i (i is 0) of the polynomial B (x).
), A multiplier 31 for multiplying by an integer less than or equal to a-1), a received signal sequence _{Rt + (n-1)} received n time slots before passing through the n clock delay circuit 22, and each coefficient of the polynomial C (x). A multiplier 32 for multiplying C _i (i is an integer of 0 or more and a-1 or less); an adder 33 for adding an input to an output of the multiplier 31; Is provided by a delay circuit 35 that provides the following.

[0023] Each output S _i of a number of coefficient calculating circuit 21 corresponds to the coefficient of the syndrome polynomial. In the communication system to which the present invention is applied, a code word of a cyclic code such as a BCH code is continuously transmitted as a transmission data string without using a frame synchronization bit on the transmission side.

On the decoding side, a syndrome operation is performed on the received data sequence, a code word division is determined based on the position where the syndrome becomes zero, and code synchronization is established. Prior to the description of the operation related to the configuration of the present invention, the following definitions are made. The moment of the received data clock t is defined as R _t, the received reception data string n bits including R _t a (tentatively regarded as the code word of the data sequence at the receiving side) as coefficients polynomial R
_It is assumed that _t (x) is expressed as in the following equation (1) (n: error correction code length).

[0025]   R_t(X) = R_{t + (n-1)}・ X^n-1+ R_{t + (n-2)}・ X^n-2+ ... + R_{t + 1}・ x + R_t                                                         … (1) In addition, the transmission side and the reception side use a known
The generator polynomial G (x) is expressed as in the following equation (2).
You.   G (x) = G_a・ X^a+ G_n-1・ X^a-1+ ... + G₁・ X + G₀                                                         … (2)

R at the instant of clock t_tN-bit
Syndrome polynomial S of received data sequence_t(X) is the above
Receiving polynomial R_t(X) divided by the generator polynomial G (x)
The remainder is given by the following equation (3).   S_t(X) = R_t(X) MOD G (x) = S_{a-1, t}・ X^a-1+ S_{a-2, t}・ X^a-2+ ... + S_{1, t}・ X + S_{0 , T}                                                         … (3)

Further, the polynomial B (x) used in the present invention,
The coefficient of C (x) is obtained in advance by a modular exponentiation as in the following equations (4) and (5). _{^{B (x) = x n MOD}} G (x) = B a-1 · x a-1 + B a-2 · x a-2 + ... + B 1 · x + B 0 ... (4)

[0028]   C (x) = X^a  MOD G (x) = C_a-1・ X^a-1+ C_a-2・ X^a-2+ ... + C₁・ X + C₀                                                         … (5) Receive polynomial R_tIn response to (x), after one clock elapses
Shin polynomial R_t-1(X) is a constant as in the following equation (6).
Be defined.

[0029]   R_t-1(X) = R_{t + (n-2)}・ X^n-1+ R_{t + (n-3)}・ X^n-2+ ... + R_t・ X + R_t-1 = XR_t(X) + R_{t + (n-1)}・ Xⁿ+ R_t-1                                                         … (6) Similarly, R_t-1Syndrome polynomial corresponding to (x)
Formula S_t-1(X) can be derived by the following equation.

[0030]   S_t-1(X) = R_t-1(X) MOD G (x) = [XR_t(X) MOD G (x)] + [R_{t + (n-1)}・ Xⁿ  MOD G (x)] + [R_t-1  MOD G (x )] = [XS_t(X) MOD G (x)] + [R_{t + (n-1)}・ B (x)] + R_t-1 = [(S_{a-1, t}・ X^a+ S_{a-2, t}・ X^a-1+ ... + S_{1, t}・ X²+ S_{0, t}X) MOD G (x)] + [R_{t + (n-1)}・ B (x)] + R_t-1 = [(S_{a-1, t}・ X^a  MOD G (x)] + [(S_{a-2, t}・ X^a-1 + ... + S_{1, t}・ X²+ S_{0, t}X)] + [R_{t + (n-1)}・ B (x)] + R_{t- 1} = [S_{a-1, t}・ C (x)] + [(S_{a-2, t}・ X^a-1+ ... + S_{1, t}・ x²+ S_{0, t}X)] + [R_{t + (n-1)}・ B (x)] + R_t-1 = (S_{a-1, t}・ C_a-1+ S_{a-2, t}+ R_{t + (n-1)}・ B_a-1) ・ x^a-1+ ... + (S_{a-1, t}・ C₁+ S_{0, t}+ R_{t + (n-1)}・ B₁) .X + (S_{a-1, t}・ C₀+ R_{t + (n-1)}・ B₀+ R_t-1) = S_{a-1, t-1}  ・ X^a-1+ ... + S_{1, t-1}・ X + S_{0, t-1}                                                         … (7)

From the above equation (7), the syndrome polynomial is
Known polynomial coefficient C_i, B_iAnd received data string, one clock
Using the syndrome polynomial before the check, the following equation (8)
Can be expressed in the form of a recurrence formula.   S_{i, t-1}= S_{a-1, t}・ C_i+ S_{i-1, t}+ R_{t + (n-1)}・ B_i                                     (I is an integer of 1 or more and a-1 or less)   S_{0, t-1}= S_{a-1, t}・ C₀+ R_t-1+ R_{t + (n-1)}・ B₀                                     (I is 0)                                                         … (8)

A circuit embodying this recurrence formula is the syndrome sequential calculation circuit 10 of FIG. Note that each register in the syndrome sequential calculation circuit 10 needs to be set to a correct value at the time of initialization (start of circuit operation), but each coefficient relating to the syndrome polynomial of the code word of n-bit continuation “0” is “ Since the value is "0", the values of the registers used in the n-clock delay circuit 22 and the delay circuit 35 may be set to "0" at the time of initialization.

Further, since the coefficients of the syndrome polynomial for n clock periods from the time of initialization are undefined, the zero detection circuit 11 performs masking using the n clock counter 13. Further, the code synchronization circuit needs to be protected in consideration of the addition of an error on the transmission path, and the frame synchronization protection circuit 12 performs synchronization protection such as forward protection and backward protection.

FIG. 3 shows the syndrome sequential calculation circuit 1 of FIG.
It is a figure explaining the code synchronous sequence of 0. As shown in the figure, since the syndrome calculation using the syndrome sequential calculation circuit 10 is a sequential process, the maximum required time is 2n− for the syndrome calculation of n times.
One clock.

That is, the conventional maximum required time is n × (n
Since +1) -1 clock is used, the time required for code synchronization can be reduced by using the code synchronization circuit of the present invention without increasing the circuit scale of parallel processing or the like. Next, as described above, in the communication system to which the present invention is applied, a code word of a cyclic code such as a BCH code is continuously transmitted as a transmission data sequence without using a frame synchronization bit on the transmission side. ing.

In the case of using such a code, a specific position (for example, the first bit) of a continuous code word is inverted and transmitted in advance, and the decoding side sequentially shifts the position of one bit inversion to obtain a correct code word. A method for detecting a cut has been proposed. Even when a codeword string using the above-described method is transmitted, the syndrome sequential calculation circuit 1 of the present invention is used.
0 operates normally, and the syndrome corresponding to the received signal sequence is calculated.

Therefore, the syndrome polynomial S ′ (x) of the code word corresponding to the code processing (eg, the first bit inversion) performed on the transmission side is calculated in advance as in the following equation (8). Keep it. ^{S '(x) = x n} MOD G (x) = S' a-1 · x a-1 + S 'a-2 · x a-2 + ... + S' 1 · x + S '0 ... (8)

[0038] _i 'each coefficient S of (x)' S is a constant.
The syndrome sequence calculated by the syndrome sequential calculation circuit 10 is compared with the above-mentioned S ′ _i, and a case where the sequence matches is determined as a code word break. FIG. 4 is a diagram showing another example of the code synchronization circuit 10 corresponding to a code word obtained by inverting a specific position of a continuous code word in advance.

As shown in this figure, as compared with FIG. 1, the syndrome detection circuit 14 for detecting the coincidence of the syndromes as described above is replaced with the zero detection circuit 11. The syndrome determination circuit 14 can also achieve the same code synchronization characteristics for codewords in which specific positions of consecutive codewords are inverted in advance.

[0040]

As described above, according to the present invention,
Syndrome calculation for detecting code synchronization is performed by sequential processing. Therefore, when the number of protection stages for preventing erroneous synchronization is not considered, the number of clocks required for code synchronization can be completed with a maximum of less than 2n clocks, and the time can be significantly reduced without increasing the circuit scale of parallel processing. There is a remarkable effect that it becomes possible.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a schematic configuration of a code synchronization circuit according to the present invention.

FIG. 2 is a diagram showing a schematic configuration of a syndrome sequential calculation circuit 10 of FIG. 1;

3 is a diagram illustrating a code synchronization sequence of the syndrome sequential calculation circuit 10 of FIG.

FIG. 4 is a diagram showing another example of the code synchronization circuit corresponding to a code word obtained by inverting a specific position of a continuous code word in advance.

FIG. 5 is a block diagram illustrating a schematic configuration of a code synchronization circuit which is a premise of the present invention.

FIG. 6 is a block diagram illustrating a schematic configuration of a syndrome calculation circuit 15 of FIG. 5;

7 is a diagram illustrating a code synchronization sequence of the syndrome calculation circuit 15 in FIG.

[Explanation of symbols]

10. Syndrome sequential calculation circuit 11… Zero detection circuit 12 ... Frame synchronization protection circuit 13 ... n clock counter 21 ... a coefficient calculation circuits 22 ... n clock delay circuit 31, 32 ... multiplier 33, 34 ... adder 35 ... Delay circuit

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-11-234252 (JP, A) JP-A-3-93317 (JP, A) JP-A-51-113506 (JP, A) JP-A-7- 115412 (JP, A) JP-A-1-272335 (JP, A) JP-A-1-274248 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) H04L 7/00 H04L 7 / 08 H03M 13/15 H03M 13/33 H04L 1/00

Claims (5)

(57) [Claims] In a code synchronization circuit for establishing code synchronization of a code word using a cyclic code, a code word division is performed from a position at which a coefficient of a syndrome polynomial of a modular exponentiation obtained by dividing a received data sequence by a generator polynomial becomes zero. establishing was consistent synchronization determines a zero detection circuit, sequentially obtains the coefficients of the syndrome polynomial in the received polynomial after one clock has elapsed relative to the moment of reception polynomial clock t for each bit input of said data string, said zero detection circuit
Bei example a syndrome sequential calculation circuit outputs to said syndrome sequential calculation circuit, a delay of n clock with respect to the bit inputs of the received data sequence
An input n clock delay circuit, and input n clocks before the clock passed through the clock delay circuit.
Received data, the highest order coefficient of the syndrome polynomial
Input and form a plurality of coefficients of the syndrome polynomial
And each of the coefficient calculation circuits includes a first known coefficient as a highest-order coefficient of the syndrome polynomial.
A first multiplier for multiplying the received data by n second clocks
A second multiplier for multiplying the number, and an output of the first multiplier to an input of each of the coefficient line circuits.
A first adder to be added, and an output of a second multiplier added to an output of the first adder.
A second adder, and a delay for delaying the output of the second adder by one clock
And the output of the delay unit is a higher-order coefficient calculation circuit.
A code synchronization circuit, which is connected to an input of a path . 2. Each coefficient S of a syndrome polynomial relating to a reception polynomial after one clock of the coefficient calculation circuit has elapsed.
_{i, t−1} are the highest order coefficient S _{a−1, t} of the syndrome polynomial, the output R _{t + (n−1)} of the n clock delay circuit, the first known coefficient B _i , and the second known coefficient C _Assuming that _i , S _{i, t−1} = S _{a−1, t} · C _i + S _{i−1, t} + R
_{t + (n−1)} · B _i (i is an integer of 1 or more and a−1 or less) S _{0, t−1} = S _{a−1, t} · C ₀ + R _t−1 + R
_2. The code synchronization circuit according to claim 1, wherein the code synchronization circuit is represented by a recurrence formula of _{t + (n−1)} · B ₀ (i is 0). 3. An n-clock counter is further provided.
The n clock counter is a syndrome sequential calculation circuit.
Cannot be used for n clock periods from the time of initialization
2. The code synchronization circuit according to claim 1, wherein detection of a road is excluded . 4. The method according to claim 1, wherein the cyclic code is a BCH code.
Wherein, the code synchronization circuit according to claim 1. 5. The syndrome detecting circuit according to claim 5, wherein said zero detecting circuit is a syndrome judging circuit.
And the syndrome determination circuit predicts at a specific position.
Syndrome code polynomials for consecutive codewords
Are calculated in advance, and the syndrome is sequentially calculated.
Comparing the syndrome sequence calculated by the circuit with the coefficient,
Judgment of matching locations as code word breaks to ensure synchronization
Characterized by standing, code synchronization circuit according to claim 1.