Device for error correction


H03M13/02 -

 

(57) Abstract:

The invention relates to computer technology and can be used in systems noiseless coding and decoding, in particular in the optical disk storage devices. The aim of the invention is to increase the information capacity of the device and its simplification. It contains five registers, buffer register, buffer exchange unit, three buffer unit, generator syndromes, two register flag, the count of erase two of the memory block locators, generator locators, multiplexer locators, the controller flag, the controller address locator, buffer block flag, buffer block locators, the zero detector signal, the register analysis, five multiplexers, memory block, the adder, arithmetical-logical unit, two comparator, the memory block is constant, encoder, Converter command, the synchronization block, the memory block commands, an instruction register, an operating bus, an information bus, the bus flag signals, a control input, the output of the address correction, control output, the control output, bus synchronization, the control bus. A device that encodes or decodes the incoming information bus received the word with which to earn a continuous stream of information. 7 Il., table 1.

The invention relates to computer technology and can be used in systems noiseless coding and decoding, in particular in the optical disk storage devices.

Known system, correcting errors [1] It contains a generator syndromes, the block memory generator locators and computing device, including arithmetical-logical unit, modulo two, the registers of the currency, multiplexers, ROM logarithms and antilogarithms, control scheme. The system performs the calculation and correct up to two errors in the code word. Its main characteristic is the generator of the locator performs the function of calculating the error locators and the reciprocal of the sum of these locators by the method of successive substitution of their values in the following equations:

f(x) x2+1x +a20 and

Sm(i+j)32mwhere1i+j;

2ij;

Smthe modified syndrome error.

However, the system suffers from the following disadvantages: it is not possible to adjust erase, i.e., unsuitable for the encoding procedure, the complexity of the gene is CLASS="ptx2">

Famous diagram of the reed-Solomon decoder [2] It contains the generator syndromes, generator locators erase ROM logarithms, antilogarithms and roots of a quadratic equation, ROM command, the memory block, the control circuit and the computing device, including arithmetical-logical unit, registers sharing and multiplexers. The scheme makes calculation and correction of any combination of errors and s, satisfying the following inequality:

2 + 1 d l, where d is the code distance Hamming;

the number of errors in the code word;

l the number of erase in the code word.

However, the scheme has the following disadvantages: the computing device comprises a ROM with great redundancy, the operations of addition and multiplication-division nesovmestny that leads to the application of ROM commands larger than 1 KB, the process of correction decoding is performed for a large number of steps, the decoder requires a complex control scheme.

Known system, correcting errors [3] which is the closest technical solution of the invention on the principle of action and the achieved result. It is designed for use in noise-immune digital systems operating with approx what about the signal, ROM logarithms and antilogarithms locators, the controller flags the control circuit, the address generator commands from the control circuit, the ROM command, the register exchange correction generator locators, the count of erase computing device, including arithmetical-logical unit, the operational registers, ROM logarithms and antilogarithms (or ROM inverse element, if the arithmetical-logical unit uses a fast multiplier and adder modulo two.

The system calculated the error syndromes and accompanying code word flags performs calculations locators errors and erase values and error correction characters. Moreover, correcting capability of the system is limited by the expression 2 + l d l. All the above operations in this system are no more than 100 steps and require amount for this ROM commands in 384 words (each word contains at least 9 bits).

However, the system suffers from the following drawbacks: a large number of ROM tables required for transformations in Galois field (28), the complexity of the controller flags and the control circuit generator addresses, inefficient use of space ROM commands.

The aim of the invention is a vet, includes generator syndromes, the first buffer unit, the first register flag, the count of erase of the first memory block locator, buffer block, locator, buffer block flags block of memory commands, the instruction register, the memory block and the zero signal detector, arithmetical-logical unit, the first comparator, information bus, the operating bus and bus flag signals inputted to the synchronization unit, the first to fifth registers, buffer register, buffer exchange unit, the second and third buffer units, generator locators, multiplexer locators, the controller address locators, the controller flag, the second flag register, Converter command, the memory block is constant, the adder, register analysis, the encoder, the second comparator and the first to fifth multiplexers, while the control inputs of the memory block constants, arithmetical-logical block, the memory block, the first to fifth multiplexers, the third to fifth registers, register analysis, the third buffer unit, the first and second Comparators and encoder combined and connected to the control bus, the control output of the inverter commands connected to the control bus, the address Converter output commands is connected to the address input unit operatively the IR-logical block connected to the second information input of the third multiplexer, the second information input connected to the output arithmetical-logical unit, the output of which is connected to the address input of the memory block is constant, the output of which is connected to the first information input of the second multiplexer, the second information input of which is combined with the second information input of the first multiplexer and connected to the output of the fifth multiplexer, the output of the second multiplexer is connected to the input block of the adder and to the information inputs of the third and fourth registers, the outputs of which are connected respectively with the first and second inputs arithmetical-logical unit and information inputs of the first and second Comparators, the outputs of which are connected to the blocking input of the adder, first input connected to the output of the third register, and the output is connected to the information input of the block RAM, the first information input of the fourth multiplexer and the input of the zero signal detector, the output of which is connected to the input register of the analysis, the output of which is connected to the second information input of the fourth multiplexer, the output of which is connected to the input of the third buffer unit, the output of which is connected to the operating bus, the output of the PE the pout input multiplexer locators, the first input of the controller flags and the first input-output buffer exchange unit connected to the operating bus, a second input-output buffer exchange unit is connected to the input of the buffer register and the output of the first register, whose input is combined with the outputs of the buffer register and the second buffer unit, with the input of the second register connected to the data bus device, the output of the second register is connected to the input of the second buffer unit and generator syndromes, the output of which is connected to the input of the first buffer unit, a control input which is combined with the control inputs of the generator syndromes, buffer block locators, encoder, controller flag Converter commands and the output of the instruction register, whose input is connected to the output of the memory block command, the control input of which is connected to the first control output of the controller flag, the second control output of which is connected to the control input of the controller address locators, the third control output is a control output, the control output of command is connected to the control input of the controller flag, the sign flag which is connected to the output of the second register flag, and the flag is control the cerned flag registers connected to the bus flag signal device, the output of the first flag register connected to the control inputs of the first memory block locators and erase counter, the output of which is connected to the second information input of the controller flag and the address input of the first memory block locators, information input connected to the output of the generator locators, and the output connected to the second input of multiplexer locators, the output of which is connected to the information input of the second memory block locators, address and control inputs which are connected to the corresponding outputs of the controller address locators, and the information output is connected with the information input buffer block locators and is output address correction device, the output of the encoder is connected to the second information input of the fifth multiplexer, a control input of the synchronization unit is an input device, and managing the address outputs of the synchronization unit connected to the bus synchronization and the address input of the memory block commands.

Comparative analysis of the prototype shows that the inventive device is modified connections of circuit elements, and the presence of new elements, namely the synchronization unit, the first to fifth registers, bugesera locators, controller address locators, controller flag, the second flag register, Converter command, the memory block constants, adder, register analysis, the encoder, the second comparator and the first to fifth multiplexers.

A new set of features allows you to apply the modified algorithm of reed-Solomon decoder, which is described next. Due to this, in the inventive device in comparison with the prototype managed to reduce the number of mapping tables in the Galois field(28and the amount of ROM commands, as well as simplified analysis of the results of intermediate calculations. All the above allows to increase the efficiency of the device and to simplify its implementation.

A comparison of the claimed technical solution with the prototype allowed us to establish the criterion of "novelty". The study of other known technical solutions in this field of technology features that distinguish the invention from the prototype, have not been identified, so they provide the claimed technical solution according to the criterion of "significant differences".

In Fig. 1 shows a diagram of the encoding procedure of Fig. 2 chart decoding procedure of Fig. 3 is a structural diagram of the CIRC decoder is aemula device, correcting errors; Fig. 7 the structure of the command word.

In Fig. 1 and 2 show one embodiment of the process of encoding and decoding for cross-alternating with reed-Solomon codes (CIRC).

In CIRC-coder processing procedure of the information which is shown in Fig. 1, is dual encoding through the use of reed-Solomon codes. For this to 24 information symbols Wi, passed through the interleaver 1, are added to the encoder 2 four test symbol Q0.Q3. Next, re-organized the code word is passed through the interleaver 3 (D multiplicity latency information), re-coded in the encoder 4, the resulting information is added four more test symbol P0. P3. The output code word is obtained by passing encoded in the encoder 4 information via the interleaver 5.

In CIRC-decoder, the procedure of information processing which is shown in Fig. 2, is the inverse interleaving the code words respectively peremerzaesh 6, 8, and 10. At the same time this is a double CIRC decoding code decoders 7 and 9, resulting in a corrected any errors. After correctionville Wi.

Block diagram of the codec, which provides the above procedure of encoding and decoding is shown in Fig. 3. CIRC-codec consists of a controller 14 controls, controller 16 of the memory unit 17 of RAM and the claimed device 15, and correcting errors. The input 11 of the codec receives signals that support its work and ensure smooth operation of the codec with external devices. The controller 14 generates a control outputs 18 and 19 of the signal transmission and reception of data sent through the inputs-outputs 12 and 13 between the external devices and internal buses (information BD and flag BFL). The controller also generates the necessary control signals for the device 15 and the controller 16 of the memory. The processing procedures are performed in block 17 of RAM on specially generated addresses and control signals from the controller 16 of the memory. For each of the elements of the procedure in block 17 memory arranged corresponding to the memory region. Forwarding information from the field in the area of memory supported on tires BD and BFL device 15. Simultaneously, the device 15 performs the function of the encoders 2 and 4 (see Fig. 1) and decoders 7 and 9 (see Islam error values and their locators. On the calculated values of locators received at the address input of the controller 16 of the flag, called from block 17 of the memory corresponding to the location of these locators erroneous symbols. After adjusting them to the device 15 is fixed characters are saved in the original location of the memory block 17. At the same time a state change occurs accompanying the code word flags by issuing the bus BFL during the overwrite information in block 17 of the memory corresponding flag values.

In the inventive device, correcting errors, the encoding mode corresponds to a decoding mode with correction of s, i.e., errors with known values of locators. Thus, in the inventive device the functions of the encoder 4 and the decoder 7 performs the decoder CI, combined with a decoder IS performing the functions of the encoder 2 and decoder 9. The difference decoders CI and CII is the length of the processed code word.

The operation of the inventive device will be understood from the following description.

All operations on the device are performed over the Galois field GF(28). The device uses a reed-Solomon code of length satisfying the following inequality:

n (281). moreover, the number of information symbol is.

For Hamming distance of this code

d 2t + 1-correcting capability of the inventive device is limited to the following inequality:

2 + l d l, where the number of errors;

l the number of erase.

Generating polynomial has the form

g(x) (x+mo) (x+mo+1) (x+mo+2).

(x+mo+2+1).

The code word represented in polynomial form,

V(x) Vo+ V1x +V2x2+ +Vn-1xn-1divided by g(x), i.e.

V(x) (mod g(x)) 0.

The received word to be decoded, can be represented as

C(x) Co+ C1x + C2x2+ +Cn-1xn-1and

(X) (mod g(x)) [V(x) + E(x)] (mod g(x)) E(x).

When this polynomial error E(x) for errors can be represented in the form

E(x)ejxij(0jn-1)

Of polynomial errors E(x) are syndromes of errors Smas

Sm- C()= E()e(0 m 2t-1).

In General, the polynomial syndromes is

S(x) Sixi< / BR>
Through the obtained syndromes in the decoding process calculates the coefficients of the polynomial locators (x) with

(x) (1+Xjx)xjwhere Xjlocator errors or erase.

The factors can be the LASS="ptx2">

Values locators X errors found during the solution of the equation

(x) 0.

After computing the error locators values of the errors found from the solution of the following equation:

(x) S(x) (x) (mod x2+)ejX(1+Xix) where e is the error value that can be represented in the form

ej(Xj) * Xj-mo+1/ (Xjfor each specific locator.

For the case t=2 and m=0, we have a generating polynomial

g(x) (x+1) (x+ ) (x+2) (x+3).

Then the equation (1) can be represented in the form

1

S1+ 1*S00;

S2+1*S10;

S3+1*S20, which implies that

1=S1/S0=S2/S1=S3/S2;

2

S2+1*S1+2*S0=0;

S3+1*S2+2*S1=0, which implies that

1=a/c=X1+X2;

2=d/c=X1*X2, (2) where

a=S0*S3+S1*S2;

f=S1*S3+S22;

c=S21+S0*S2.

To solve system (2) is a well-known method of solving quadratic equations through a table-valued function with a variable (21*y;

X2=X1+1.

If we take as a basis the assertion that

z*0= z/0= 0/z=0/0=0, (3) the expression for1in system (2) can be represented as

1= S1/S0+(c*S1/S0+a)/c, then for two and one error you can use the same decoding algorithm (the so-called modified algorithm of decoding errors). This leads to increased efficiency and reduction software decoder.

The modified algorithm of calculation errors is shown in Fig. 4.

The algorithm for computing s (see Fig. 5) for a known array of locators erase [Xi] are based on solving a system of linear equations for syndromes with regard to the previously accepted claim (3).

The repair information is in the following operations:

Vi=Ci+ei.

Structural diagram of the inventive device shown in Fig. 6. It contains the first register 20, the buffer register 21, the buffer unit 22 of the currency, the second register 23, the second buffer unit 24, the generator 25 syndromes, the first buffer unit 26, the first register 27 of the flag counter 28 erase the first block 29 memory locators, generator - tor 30 Loka is tori, the second register 35 flag, the buffer unit 36 flags, buffer unit 37 locators, the detector 38 zero signal, the register 39 analysis, the fourth multiplexer 40, the third buffer block 41, block 42 of RAM, an adder 43, the fifth register 44, the third multiplexer 45, arithmetical-logical unit 46, the third register 47, the fourth register 48, the first multiplexer 49, the first comparator 50, the second comparator 51, the second multiplexer 52, block 53 memory constants, the fifth multiplexer 54, the encoder 55, the inverter 56 commands, block 57 synchronization block 58 memory commands, the register 59 teams, operating bus 60, the information bus 12, the bus 13 of the flag, the control input 61, the output 62 address correction, control output 63, the control output 64, bus 65 synchronization bus 66 of the control.

The device, correcting errors, works as follows.

The control input 61 produced initial installation and subsequent start of block 57 synchronization installation which produces pulses, the signals of the currency, addresses, commands and clock frequency for the internal components of the device.

Processing the code word is made from two decoders CI and CII for two frames (duration 588 cycles each). In the first katolickiego code which generator 25 syndromes produces the following recursion:

SkCiSk*k. where k 0, 1, 2, 3;

i 0.(N-1). and for CI, N=32, and for CII N=28.

The processed symbols corrected code is issued to the bus 12 via the buffer unit 24 for recording in the area of CI or CII external memory. At the same time, it calculates the number of erase and their locators. This flags s with tires 13 are recorded in the register 27. If the flag of the logical level "1" is the status of the counter 28 and the generator 30 locators, with previous information from the generator locators is written in block 29 of the memory. The processed flag register 27 outputs on bus 13 to record in the area of CI or CII external memory.

Upon completion of the processing of the first code word calculated values of the syndromes are overwritten in the internal memory of the generator 25 syndromes, then they can be issued on an operating bus 60 via the buffer unit 26, the values of the locators are overwritten from the block 29 to the memory via the second input of the multiplexer 31 in block 34 of the memory regardless of the state at its address inputs, and the value of the counter 28 erase the internal memory of the controller 32 of the flag. After that, the generator 25 syndromes, schachtian syndromes locators and the number of erase in the second frame, the computation of the true error values Yiand their locators with subsequent correction code word.

The algorithms consist of a four-cycle operations the calculation performed in the following way. The first operand A is recorded on the first beat in the register 47 from the output of the multiplexer 49, the second operand B is recorded on the second beat in the register 48 from the output of the multiplexer 49.

After the second stroke, the result of the addition of the first and second operands in arithmetical-logical unit 46, which represents the modulo 255, passing through the second input of the multiplexer 52, the memory block is constant and the second input of the multiplexer 49, enters the blocked entrance of the adder 43. Blocking occurs if the input of one of the Comparators 50 and 51 filed operand corresponding to the value 255, which allows to realize the condition (3). In the adder 43 is the addition of the above mentioned result of the addition of the first and second operands with the third operand C, recorded in the register 44 in the third bar. The result of the calculation operations in the fourth step can be written in block 42 memory 16 bytes or issued to the operating bus 60 through the second input is the sector 38 zero signal, then the result of the analysis can be recorded in the register 39, which applies the serial register. Information about the state of the register 39 analysis can be issued via the first input of the multiplexer 40 and the buffer block 41 on the operating bus 60. Moreover, the buffer block 41 can be opened only in the fourth step of the operation.

The multiplexer 52 allows you to skip through the table memory operands from memory unit 42 in the first and second cycles of the above-mentioned calculation. To reduce the calculation time in the zero cell of the memory unit 42 stores a constant number 0.

Block 53 memory contains the following conversion table in the field GF(28): the field element in the room designated element of the field number of the field element in the element field, the value of the seat element field value from a table of roots of a quadratic equation, repetition (the item in the identical item).

The calculation operation is characterized by the following mathematical functions on operands:

A * B + C;

A / B + C.

Thanks to the multiplexers 45 and 49 of the calculation can be performed on operands taken from block 42 of RAM, and over the operands, Postup is yet encryption function, shaping the values of non-designated locator in the code word.

The function of the inverter 56 teams is the conversion command word received from the output register 59 commands, synchronization with bus 65 to the control signals on bus 66 management, and address of block 42 of RAM that supports the calculation. In the format code words shown in Fig. 7, the discharge INS7 specifies the source operand used in the calculation, i.e., either block RAM or bus 60. Command BLOCK are unlocking in the adder 43 and the module adder 46. Team ALU includes one of the modes of operation of the adder 46, namely either summation or subtraction. If there comandi in the register 39 is written to the result of the analysis at 0, the data resulting from a calculation. Team GOTH information from the register 39 is supplied to the bus 60, and simultaneously, the controller 56 to the gate of the transfer of the results of the analysis in the controller 32 of the flag. The EXT command allows the fourth step of the calculation to be connected to the bus 60 external sources. Command table ROM" initialize the inclusion of one of the block table 53 memory constants.

The result of the analysis is to as in the memory unit 34, and in the controller 32, where it is tested for membership of his many locators code words. The locators from the block memory 34 may be issued on the bus 60 via the buffer unit 37, and the output 62 of the address correction.

Once the calculation of the error values and their locators to the address displayed on the output 62, made the call from the external unit 17 RAM corrected symbol, which via the bus 12, the register 20 and the buffer unit 22 of the currency enters the device, where it is added modulo two with a value of Yi. Next, the corrected symbol via the buffer units 22 and 21 is issued to the bus 12 and stored in the original location of the block 17 of RAM.

In the device register 20 and the buffer block 21 between corrections are used to support the exchange of information over the bus 12.

The output 63 of the controller 32 can block correction if the number of errors exceeds the correcting capabilities of the device. For this purpose, the output 63 is connected to the controller 16 external memory with the output 62 of the address correction.

The controller 32 makes the final decision about the possibility of correction of errors on the ratios of the results of the analysis of the m word and also initializes flags. For broadcast previously set flags used by the register 35, the host flags with bus 13 flag. Initialized flags go through the buffer unit 36 to the bus 13 to record to an external unit 17 of RAM.

Processing results of the analysis begins with the following reassignment:

b0=a0/ a3;

b1=a1*a2.

Next, taking into account the state of the internal flag register that stores information previously calculated in the counter 28, the number of flags F0(NF0for decoder CI, and flags F0(NF0and F1(NF1for decoder CII controller 32 in accordance with table decoder errors and the algorithm generates the command permissions correction (k) received at the output 66, and flags for channels F0and F1for decoder CI and F0F1and F2for decoder CII issued on the control output 66 and then to the bus 13.

To switch programs (erase or errors) in block 58 of the memory commands from the controller 32 at its control input the appropriate signal is received.

Experimental work of the claimed device, correcting errors in SOS is a logical destination (prototype) of the claimed device allows more efficient use of program resources, i.e., dramatically reduced the amount of used ROM, and greatly simplifies its implementation that allows you to successfully implement the claimed device on a semi-custom CMOS matrix ENCORE with a small degree of integration.

DEVICE FOR ERROR CORRECTION, comprising a generator of syndromes, the first buffer unit, the first register flag, the count of erase of the first memory block locator, buffer block, locator, buffer block flags block of memory commands, the instruction register, the memory block and the zero signal detector, arithmetical-logical unit, the first comparator, information bus, the operating bus and bus flag signals, characterized in that, to increase the information capacity of the device and its simplification, it introduced the synchronization unit, the first to fifth registers, buffer register, buffer exchange unit, the second and third buffer units, generator locators, multiplexer locators, the controller address locators, the controller flag, the second flag register, Converter command, the memory block is constant, the adder, register analysis, the encoder, the second comparator and the first and fifth multiplexers, control inputs of the memory block constants, arithmetical-logical unit block operativnoy, the first and second Comparators and encoder combined and connected to the control bus, the control output of the inverter commands connected to the control bus, the address output connected to the address input of the memory block, the output of which is connected to information inputs of the first and third multiplexers, the output arithmetical-logical unit connected to the second information input of the third multiplexer, a second information input connected to the output arithmetical-logical unit, the output of which is connected to the address input of the memory block is constant, the output of which is connected to the first information input of the second multiplexer, the second information input of which is combined with the second information input of the first multiplexer and connected to the output of the fifth multiplexer, the output of the second multiplexer is connected to the input block of the adder and to the information inputs of the third and fourth registers, the outputs of which are connected respectively with the first and second inputs arithmetical-logical unit and information inputs of the first and second Comparators, the outputs of which are connected to the blocking input of the adder, a first input connected to the output of the third p is otwartego multiplexer and the input of the zero signal detector, the output of which is connected to the input register of the analysis, the output of which is connected to the second information input of the fourth multiplexer, the output of which is connected to the input of the third buffer unit, the output of which is connected to the operating bus, the output of the first buffer unit, the first information input of the fifth multiplexer, the output buffer block locators, the first multiplexer input locator, the first input of the controller flags and the first input-output buffer exchange unit connected to the operating bus, a second input-output buffer exchange unit is connected to the input of the buffer register and the output of the first register, input is combined with the outputs of the buffer register and the second buffer unit, with the input of the second register connected to the data bus device, the output of the second register is connected to the input of the second buffer unit and generator syndromes, the output of which is connected to the input of the first buffer unit, a control input which is combined with the control inputs of the generator syndromes, buffer block locators, encoder, controller flag, a drive command and the output of the instruction register, whose input is connected to the output of the memory block command, the control input of which is connected to p the TAC controller address locators, the third control output is a control output, the control output of command is connected to the control input of the controller flag, the sign flag which is connected to the output of the second register flag, and the flag is a control output connected to the input of the buffer block flag, the output of which, as well as inputs of the first and second flag registers connected to the bus flag signal, the output of the first flag register connected to the control inputs of the first memory block locators and erase count, the output of which is connected to the second information input of the controller flag and the address input of the first memory block locators, an information input connected to the output of the generator locators, and the output connected to the second input of multiplexer locators, the output of which is connected to the information input of the second memory block locators, address and control inputs which are connected to the corresponding outputs of the controller locator, and information output is connected with the information input buffer block locators and is output address correction device, the output of the encoder is connected to the second information input of the fifth multiple the synchronization connected to the bus synchronization and the address input of the memory block commands.

 

Same patents:

The invention relates to computing and communications

The invention relates to a device for the encoding of discrete messages and can be used in FSO communication systems

The invention relates to a remote control and pulse technique and can be used in the transmission and processing of discrete information for error correction in communication channels

The decoding device // 2007866
The invention relates to communication technology, and in particular to devices for decoding information encoded block correction code, and can be used in communication systems with replay code words

The invention relates to a multi-valued error-correcting coding for the protection of the transmitted channel information from failures caused by interference
Up!