A device for decoding a bch code with correction triple error

 

(57) Abstract:

The device may be used in computing and telecommunications at the receiving side communication systems for encoding binary codes. In the decoding device containing the residue computing unit, connected to a unit for computing the coefficients of a polynomial that contains the register drive address register, the ROM constants and logarithms and RAM, as well as offset error carrying out the procedure of Chen with the purpose of correcting three or less errors in the input sequence, to increase performance and reduce hardware costs are entered matrix circuit receiving syndromes and specific values for the solutions of the polynomial that gives the possibility to exclude the ROM and RAM. 3 Il.

The invention relates to computer technology, telecommunication and can be used at the receiving side communication systems for encoding binary.

A device decoding correction not more than two errors [1] , comprising a shaping circuit syndromes S1 and S3 from the input code sequence, diagrams, calculations, S1 and S3, summation scheme (S1 + S3), the procedure of Chen for solving polynomial

I(x) = S1x2+ whom this device is to limit the number of corrected errors.

Closest to the proposed is a device for decoding a BCH code [2] with correction triple error-containing residue computing unit, coupled to the computing unit coefficients1,2,3containing the register drive address register, the ROM constants and logarithms and RAM, and the offset error carrying out the procedure of Chen with the purpose of correcting three or less errors in the input code sequence. This involves the solution of a polynomial

(x) = 1 +a1x +a2x2+3x3, (1) where1= S1;2= (S2S3+S5)/(S1S2+S3);3= S1S2+S3+[(S2S3+S5)S1/(S1S2+S3)] .

If the value of a polynomial for a given position of the input code sequence is not equal to zero, the generated correction the correction signal has a low level. If the value of the polynomial is zero, then the correction signal has a high level. He summed across mod2 with the input code sequence and changes its value to the opposite.

The disadvantage of this device is the necessity of addressing the ROM and RAM in the calculation of the coefficients1, 2,3in the computing unit of the factors that limit the speed of decoding and triene hardware costs to implement the device decoding a BCH code with correction triple and less error by excluding the operation of finding the logarithm and antilogarithm syndromes S1, S2, S3, S5, when calculating odds1,2,3that allows you to refuse the use of ROM and RAM.

The aim is achieved in that in the transmitter coefficients are input matrix circuit receiving syndromes S2, S3 and S5 and values (S1S2 + S3)S1 S2S3 + S5 and (S1S2 + S3)2+ +S1 S2S3 + S5) for solving polynomial

*(x) = A +a1* x +a2* x2+3* x3, (2) where A = S1S2 + S3;

1* = (S1S2 + S3)S1;

2*= S2S3 + S5;

3* = (S1S2 + S3)2+ S1 S2S3 + S5), in order to perform the procedure of Chen in the error corrector for correcting triple and less error in the input code sequence.

In Fig. 1 shows a structural electrical diagram of the device. The device comprises a block 1 calculate the residue, consisting of registers 2, 3, 4 with feedback, each of which input is connected to the input device and output to the inputs of buffer registers 5, 6, 7 storage residues, respectively, block 8 calculation of the coefficients, consisting of a matrix of multipliers 9, 10, 11 receive syndromes S2, S3, S5 of the residue multipliers 12, 13 receive works S1S2 and S2S3 respectively, adders 14, 15 receive amounts mod2 S1S2 + S2S3 S3 and + S5, respectively, multipliers 16, 17 to obtain (S1S2 + S3)S1 and (S2S3 + S+ S3)2+ +(S2S3 + S5)S1, block 20 error corrector consisting of buffers 21, 22, 23, 24, 25 storage syndrome S1 and the coefficients A,1*,2*, 3*accordingly, the circuit 26 of the control of the multipliers 27, 28, 29, 30, adders 31, 33 mod2 and circuits 32, 34.

The device operates as follows.

To the input unit 1, the calculations of residues receives an input code sequence and divide it by the minimum polynomial of the code. For example, for a BCH code of length 255 [3]

m1(x) = x8+ x4+ x3+ x2+ 1;

m3(x) = x8+ x6+ x5+ x4+ x2+ x + 1;

m5(x) = x8+ x7+ x6+ x5+ x4+ x + 1.

The block contains three shift register with feedback, implement the division of minimal polynomials, as well as buffer registers for storing the residues R1, R3, R5 (Fig. 1.18 of [2] ). The values of the residues R1, R3, R5 are received in block 8 of the calculation of the coefficients, consisting of matrices of combinatorial logic that performs the multiplication and summation mod2 in the Galois finite field GF(2m). Matrix multipliers 9, 10, 11 for receiving the syndromes S2, S3, S5 of the residues R1, R3, R5 represents a matrix of interconnected aceea R1 must be multiplied by the matrix

1 0 0 0 1 0 1 1

12468101214____> 0 0 0 0 0 0 0 1

0 1 0 0 1 1 1 0

0 0 0 0 1 0 1 0

0 0 1 0 1 1 0 1

0 0 0 0 0 1 0 0

0 0 0 1 0 1 1 0

0 0 0 0 0 0 1 0 where is a primitive element of GF(28), built with minimal polynomial m1(x) = x8+ x4+ x3+ x2+ 1. Similarly, for S3, the remainder should be multiplied by the matrix

1 0 0 0 1 0 1 1

136912151821____> 0 0 0 1 0 1 0 0

0 0 0 0 1 1 1 1< / BR>
0 1 0 1 1 0 1 0

0 0 0 1 0 0 0 1

0 0 0 1 0 1 1 1

0 0 1 0 1 0 0 1

0 0 0 0 1 0 0 0

For S5 the remainder of R5 must be multiplied by the matrix

1 0 0 0 0 1 0 0

15101520253035____> 0 0 0 1 0 1 0 0

0 0 1 1 1 0 0 1

0 0 0 0 0 0 0 1

0 0 1 0 1 0 0 1

0 1 1 1 1 0 1 0

0 0 1 0 0 0 1 0

0 0 0 0 1 0 0 1

Example obtain S2 of R1 shown in Fig. 2A. In Fig. 2B shows a functional logic diagram of the cell of the matrix multiplier. Matrix to obtain S1 of R1 is single, so S1 coincides with R1.

Syndromes S2, S3 with matrix multipliers 9, 10 and the syndrome S1 from the output buffer register 5 is deposited on the circuit matrix multipliers of the elements of the field (APA) 12 and 13, carrying out the multiplication syndromes S1S2, S2S3 the meet the UB>1(x) field, i.e., simultaneously performs the multiplication of two polynomials and dividing them by the minimal polynomial of the field. An example implementation of APA for the field GF(28) shown in Fig. 3 and is a regular matrix of cells, described above, multiplying two elements of the field b and C.

From the outputs of the multipliers 11, 12, 13 the results of the multiplication are received at the inputs of the adders 14 and 15 mod2 performing a bitwise sum modulo two without transferring S1S2 + S2S3 S3 and + S5, respectively. With inputs of the register 5 and adders signals arrive at the inputs of the multipliers 16, 17, performs multiplication (S1S2 + S3)S1, (S2S3 + S5)S1, and the input circuit 18 that performs squaring the magnitude S1S2 + S3. These operations are performed similarly to the multiplication of field elements using MOP, as described above. From the outputs of the multiplier 17 and scheme 18 the results of the multiplication is fed to the input of the adder 19, which is a bitwise summation mod2 (S1S2 + S3)2+ (S2S3 + S5)S1.

The calculated values of the coefficients are received in block 20 of the offset error, which is the procedure of Chen. The values S1, A,1*,2* ,3* written in the buffer registers 21-25. At the same time in the circuit 26 management analyzes the value of the sum of S1S2 + S3 and produces an output signal which Yes has been less than two errors, and the solution of polynomial (2) is false. For decoding thinned code offset error must have two modes of operation. In single step on each step in the multiplier 27 is multiplication1* in dual mode step - on2. Similarly, in the multiplier 28 is multiplication2* on2or4in the multiplier 29 multiplies3* on3or6. At the same time in the multiplier 30 is multiplied S1 or2to solve polynomial

G(x) = 1 + S1x for cases where there have been less than two errors.

Multipliers 27-30 consist of registers with feedback and mod 2 adders (Fig. 1.24 of [2] ). From the outputs of the multipliers 27, 28, 29 the results of the multiplication is coming to the adder 31 mod2 to calculate the value of the polynomial (2), the output of which a signal of high level when *(x) = 0. He entered the scheme And 32 forming the output signal correction when at its second input signal of high level from the circuit 26 controls. From the outputs of the multiplier 30 is the result of the multiplication is fed to the input of the adder 33 calculate the value of the polynomial (3), the output of which a signal of high level whenI(x) = 0. He postopera to the second input circuit And 34 filed with the circuit 26 inverted signal of high level.

Thus, for each code sequence output the correction signal is a signal from the output of the circuit 32 or schemes And 34.

The use of the invention reduces the hardware cost for decoding a BCH code with correcting three errors, which means that the implementation of the decoder for an ENCORE. (56) 1. Peterson, U. , Weldon E. Codes, combing errors, M. : Mir, 1976.

2. The study group of networking equipment transmission and reception of digital television signals and sound. Report on research work. N GOS. re. 01880008588, Lanier, Leningrad.

3. Lanes B. A. , C. K. Rushforth Acellular array multiplier for GF(2). IEEE Trans. of Comp. - 1971, N 12, p. 1573-1575.

A DEVICE FOR DECODING a BCH CODE WITH CORRECTION TRIPLE ERROR containing block calculate the residue, consisting of the first and third registers with feedback inputs which are combined and input device, the outputs of the registers are connected to the inputs respectively of the first third of the buffer register of the computing unit residues whose outputs are connected respectively to the first to third inputs of the unit for computing the coefficients of the first - third the outputs of which are connected respectively to clucene to the inputs respectively of the first the third multiplier coefficients, the outputs are connected to first to third inputs of the first adder modulo two inputs of the first third of the buffer register are respectively first to third inputs of the error corrector, characterized in that, to simplify and improve the performance of the device in the offset errors introduced fourth and fifth buffer registers, the control, the fourth multiplier coefficients, the second modulo two and the first and second elements And the outputs of the fourth buffer register connected to the input of the fourth multiplier coefficients whose outputs are connected to inputs of the second adder modulo two, the output of which is connected to the first input of the first element And the outputs of the fifth buffer register connected to the inputs of the control and the fourth inputs of the first adder modulo two, the output of which is connected to the first input of the second element And the direct and inverted outputs of the control is connected to the second inputs respectively of the second and first elements And the outputs of which are combined and the output of the error corrector, the inputs of the fourth and fifth buffer registers are respectively the fourth and fifth inputs correctly - the third matrix multipliers, the first to fourth multipliers, the first through third adders modulo two and a Quad splitter, the input of the first matrix multiplier combined with the first inputs of the first and third multipliers and is the first input of the computing unit coefficients and connected to the fourth input of the error corrector, the outputs of the first matrix multiplier connected to the first input of the fourth multiplier and the second input of the first multiplier, the outputs of which are connected to first inputs of the first adder modulo two, the outputs of which are connected to the fifth input of the error corrector, the second inputs of the second multiplier and the inputs of the Quad, the outputs of which are connected to first inputs of the second adder modulo two, the output of which the output of the second multiplier are respectively the second and first outputs of the computing unit coefficients, the outputs of the second matrix multiplier connected to the second input of the first modulo-two and the second input of the fourth multiplier whose outputs and the outputs of the third matrix multiplier connected respectively to first and second inputs of the third modulo two, the outputs of which are the third outputs of the computing unit coefficients and podklady two.

 

Same patents:

FIELD: Witterby algorithm applications.

SUBSTANCE: system has first memory element for storing metrics of basic states, multiplexer, capable of selection between first and second operating routes on basis of even and odd time step, adding/comparing/selecting mechanism, which calculates metrics of end states for each state metric. Second memory element, connected to adding/comparing/selecting mechanism and multiplexer is used for temporary storage of end states metrics. Multiplexer selects first operating route during even time steps and provides basic states metrics, extracted from first memory element, to said mechanism to form end state metrics. During odd cycles multiplexer picks second operating route for access to second memory element and use of previously calculated end state metrics as metrics of intermediate source states.

EFFECT: higher efficiency.

2 cl, 9 dwg

FIELD: communications engineering.

SUBSTANCE: proposed device and method for mobile code-division multiple access communication system including device for transferring channel of backward-link transmission speed indicator afford generation of optimal code words ensuring optimal coding for all types of coding procedures from optimal type (24.1) up to optimal coding procedure 24.7 and supporting all optimal-coding devices.

EFFECT: optimized capacity.

74 cl, 21 dwg, 44 tbl

FIELD: communications engineering; network remote measuring and control systems.

SUBSTANCE: proposed noise-immune cyclic code codec designed for data transfer without pre-phasing has on sending end code-word information section shaper incorporating shift-register memory elements, units for computing verifying parts of noise-immune code of code-word information section, and modulo two adder of code-word information section shaper; code-word synchronizing section shaper and modulo two adder of code-word synchronizing section; on receiving end it has binary filter incorporating binary-filter shift register memory elements, computing units for verifying parts of binary-filter noise-immune code, and binary-filter modulo two adder; shift register of code word information section; decoder; accumulator; error correction unit; unit for shaping synchronizing section of code word; and modulo two adder units.

EFFECT: enhanced speed of device.

1 cl, 1 dwg

FIELD: communications engineering; network remote measuring and control systems.

SUBSTANCE: proposed noise-immune cyclic code codec designed for data transfer without pre-phasing has on sending end code-word information section shaper incorporating shift-register memory elements, units for computing verifying parts of noise-immune code of code-word information section, and modulo two adder of code-word information section shaper; code-word synchronizing section shaper and modulo two adder of code-word synchronizing section; on receiving end it has binary filter incorporating binary-filter shift register memory elements, computing units for verifying parts of binary-filter noise-immune code, and binary-filter modulo two adder; shift register of code word information section; decoder; accumulator; error correction unit; unit for shaping synchronizing section of code word; and modulo two adder units.

EFFECT: enhanced speed of device.

1 cl, 1 dwg

FIELD: communication systems.

SUBSTANCE: method includes generating sets of sub-codes of quasi-additional turbo-codes with given encoding speeds, and given sub-codes are reorganized as a set of sub-codes with another encoding speed for use in next transfer of sub-code with given encoding speed.

EFFECT: higher efficiency.

9 cl, 13 dwg

FIELD: data transfer technologies.

SUBSTANCE: method includes segmentation of length N of quasi-complementary turbo-codes on preset amount of sections, determining identifiers of sub-code packets appropriate for segmented portions, setting of said packets separated for initial transfer of sub-code, calculation of number of remaining symbols in form N-Fs, where N - length of quasi-complementary turbo-codes, and Fs - position of start symbol of sub-code of quasi-complementary turbo-codes, determining position of symbol of remaining symbols in amount equal to sub-codes amount, which have to be sent and serial transfer of sub-code symbols from position of starting symbol Fs to position of last symbol Ls.

EFFECT: higher efficiency.

5 cl, 17 dwg

FIELD: communications engineering.

SUBSTANCE: method includes selecting one combination among given combinations, appropriate for several or every generated symbols of code word to transmit generated symbols of code word with length of sub-packet, determined in accordance to data transfer speed, information, appropriate for data transfer speed, is read, also based on length of sub-packet and chosen combination, from a table, wherein identification information, pointing at data transfer speed, sub-packet length and selected combination, is, is previously displayed for given information, and generated code word symbols are transmitted in accordance to read information and in accordance to selected combination.

EFFECT: possible check transmission of information by means of hybrid automatic repeat query for increasing carrying capacity during high-speed information transfer.

4 cl, 16 dwg, 6 tbl

FIELD: communications engineering; simulating digital communication channels with separate and grouping errors.

SUBSTANCE: proposed method includes evaluation of set of communication channel states S0,S1, ..., Sm - 1 and calculation of conditional error probabilities P(e/s) in each state s" i = 0, ..., m - 1 of communication channel, and error acquisition in communication channel in compliance with conditional error probability for current state of communication channel; in the process probability of error-free interval p(0i) of i bits is found, and conditional probabilities p(0i1/11), p(0i1/01) of error-free intervals of i bits are calculated with respect to them basing on probabilities p(0i) and using recurrent rules during each current time interval and preceding one on condition that for error generation use is made of two states of communication channel corresponding to combination of errors 11 or 01; random number p uniformly distributed within interval between 0 and 1 is generated; conditional probabilities p(0i1/11), p(0i1/01) are summed up starting from i = 0 resulting in sequence 0k1 that constitutes bit-by-bit stream of communication channel errors.

EFFECT: enhanced speed.

1 cl, 1 tbl

FIELD: communications engineering; data transfer, telemetering, and telecontrol systems.

SUBSTANCE: proposed codec has on sending end code-word data part shaper whose output and that of code-word synchronizing part shaper are connected to modulo two adder input; on receiving end it has binary filter whose code-word data part shaper output is connected to accumulator connected to synchronizing sequence decoder and to error connection unit whose outputs are connected to respective inverting inputs of code-word data part shaper; output of the latter functions as data output of device; output of binary-filter code-word synchronizing part is connected through switching unit to input of code-word data part shaping unit; synchronizing sequence decoder output is connected to control input of switching unit and to error correction unit input; on receiving end accumulator outputs are connected to inputs of code-word data part shift decoder whose output is connected to input of delay circuit whose output functions as second control input of switching unit and as synchronizing output of device.

EFFECT: enhanced noise immunity.

1 cl, 1 dwg

FIELD: coding in communication systems.

SUBSTANCE: proposed partial reverse bit-order interleaver (P-RBO) functions to sequentially column-by-column configure input data stream of size N in matrix that has 2m lines and (J - 1) columns, as well as R lines in J column, to interleave configured data, and to read out interleaved data from lines.

EFFECT: optimized interleaving parameters complying with interleaver size.

4 cl, 7 dwg, 3 tbl

Up!