The device for decoding reed - solomon code

 

(57) Abstract:

The invention relates to telecommunication and computer engineering and can be used to enhance noise immunity in the transmission and processing of digital information, in particular in digital video recording. The aim of the invention is to increase the noise immunity reed-Solomon code. This goal is achieved by introduction to the operation unit 13 storing a value of erase block 14 of storing a value of the syndrome 14, block 15 calculation of the error locator 15, block 16 forming mask and unit 17 fixes erase providing additional detection part single and more errors in the presence of erase and part two times and more errors in the absence of erase. 2 Il.

The invention relates to telecommunication and computer engineering and can be used to enhance noise immunity in the transmission and processing of digital information, in particular in digital video or audio.

In CCIR recommendations 657 digital video for security video from errors is proposed to use a reed-Solomon code (32.30) (Khleborodov Century A. international recommendation on digital video recording. Videoanimation bytes (k) and the 32 - the total number of bytes (n), including 2 test (n - k). And (n - k) check bytes are obtained from the information as the remainder of division of a polynomial of information bytes by the generating polynomial of Galois field GF(28)

f(x)= x8x4x3x2x0.

A device for decoding reed-Solomon code, which contains blocks of computing and cyclic conversion syndromes, buffer storage, the first, second and third blocks adders, the first, second and third code converters, the first and second adders, the counter, the first decoder, the trigger, the first and second blocks of keys, information and control inputs and outputs, and first and second inputs of the synchronization. Moreover, the computing unit syndromes, first, second and third outputs of which are connected to respective inputs of the block cyclic conversion syndromes, first, second and third outputs of which are connected respectively with the first, second inputs of the first block of adders and the first input of the second unit adders, buffer storage, the information outputs of which are connected with the first inputs of the third block of adders, the trigger and the first block of keys, the outputs of which are connected to Sharomov United and are the corresponding information input device, the synchronization input of the trigger and the input synchronization buffer storage, the unit for computing the syndromes and block cyclic conversion syndromes and United are the first synchronization input device, second input synchronization buffer storage, the unit for computing the syndromes and block cyclic conversion syndromes are combined and the second synchronization input device, a counter, a counting input and a control input of the buffer memory are combined and the control input of the first and second inputs of the synchronization counter is connected to the same inputs of the synchronization device, the outputs of the counter are connected to the inputs of the first decoder, the output of which is connected to the information input trigger direct and inverted outputs of which are connected with the first and second information inputs of the second block of keys, the first output of which is connected to the control input of the first unit key outputs of the first and second block adders are connected through the same converters code with the same inputs of the first adder, the outputs of which through the third code Converter connected to the first inputs of the second adder, the second input of which is a mini-conversion syndromes the outputs of the second adder connected to information inputs of the first block of keys, the outputs of the third block of adders and the second output of the second block of keys are respectively the information and control outputs of the device.

The decoding device operates as follows.

From the incoming to the input of the decoder sequence defined syndromes S0, S1, S2 and counts the number of flags s N that accompany erased bytes. If the number of erase N = 1 or 2, the calculated error values in the erased bytes, and is their correlation. In other cases, all the information bytes are transferred to the output together with the flags (if more than two) or without them, if the flags were not.

The disadvantage of the prototype is that his scheme is the only fix two erase.

The aim of the invention is to increase the noise immunity decoding device due to partial determine two or more errors in a block and erasing (masking) in the event of this situation, an entire block.

This objective is achieved in that the device for decoding reed-Solomon code containing the key block, and the blocks of the STS; the control input device is connected to the input of the erase counter; the first synchronization input device connected with the first inputs of the synchronization blocks calculate syndromes, buffer storage and erase counter; a second synchronization input device connected to the second inputs of the synchronization unit calculating syndromes and erase counter; output buffer memory connected to the first input of the adders, the output of which is an information output device, the entered unit storing a value of erase block memory syndrome values S0, the unit for computing the error locator and block the formation of the mask.

Justification additional error detection of two or more of the multiplicity are the following theoretical background.

As is known, the decoder code (32, 30) reed-Solomon in its corrective properties allows the warranty to correct a single error (i.e., one erroneous byte of the 32 without a mask, and the number of erase N = 0) or correct no more than two erase (i.e., one or two marked erase byte).

In Fig. 1 shows the General decoding algorithm code (32, 30), where we considered all possible situations that can voznikayushchego videotrack Studio digital video recorder. Final report on the subject 052-89-09 performed under contract with the Spa (scientific production Association, state reg. N 018900 38301, LEES, 1990). From the algorithm it follows that the masking of the entire output block without error correction or erase occurs when only one of the syndromes is non-zero (S1 or S0) and the block does not contain flags erase. This situation can occur if the unit will be two or more errors. In addition, if the block has the same Erasure (N = 1) and the equation S0 * X1 = S1 fails, this indicates the presence of but one erase block of one or more errors that can be observed by masking the entire block. And, finally, the entire unit can be masked when in repair mode single error equation was not performed in any of the 32 clock cycles, which also indicates the error more than once.

The novelty and distinctive features of this device compared with the prototype is that you enter the unit of storing a value of erase block memory syndrome values S0, a block of memory error locator unit repair erase, block the formation of masks that can improve the noise immunity decoding device for scheile 1 or more in the presence of s, while maintaining the ability of the prototype to correct two erasures. Thus, there are distinctive features in comparison with the prototype, and therefore, the proposed device meets the criteria of "novelty."

However, the applicant does not know the technical solution proposed uses distinctive features to improve noise immunity. Therefore, differences between the proposed device can be considered "significant".

In Fig. 2 shows the structural diagram of the proposed decoding device.

It contains a computing unit syndromes 1 and the block buffer memory 2, the inputs of which are combined and the information input device 3, the control input (s) 4 is connected to the input of the erase counter 5, the output of which is connected with the third input is entered the display unit single error 6, the first and second inputs of which are connected to respective outputs of the computing unit syndromes 1. The first synchronization input 7 is connected to the blocks 1, 2 and 5. The second synchronization input 8 is connected to the blocks 1 and 5. The first input of the adders 9 connected to the output of the buffer memory 2, the second input of the adders 9 is connected to the output of the entered block OR 10, the first input of which is connected to the output of the block of keys 11. The output of block Summaty connected to the control input 4, and the output unit 13 is connected to the fourth input of the entered unit 17 fixes erase. Entrance entered in block 14 remember S0 is connected to the first output unit 1, and the output unit 14 is connected in parallel to the first input of the entered unit 15 to calculate the error locator and third input keys 11, the second input is connected to the output unit 15 to calculate the error locator and the first input unit 11 of keys connected to the second output of the display unit single errors, the first output of which is connected to the second input entered in block 16 of mask formation, the first input of which is connected to the second output unit 17 fixes erase, the first output of which is connected to control inputs of the blocks 5, 6 and 13. The output of block 16 is a control output device 18.

Diagram of the device is as follows.

When input 3 device information and testing works are written in the buffer tank 2 and at the same time in block 1, the computation of the syndromes S0 and S1. At the same time is counted by the counter 5 number of erase N received at the input 4 of erase. If S0 and S1 are equal to zero, then this means that errors in the block there and it is displayed on the output 12 (see Fig. 1). Elitsa single error, its latitude X1 = S1/S0. Thus, if successive reads of the block from the buffer memory of the decoder on one of the 32 clock cycles to be executed equality S0 * X1 = S1, it means there is a single error and it is corrected by adding to this erroneous bytes syndrome S0. However, if none of the 32 cycles this equality is not satisfied, it means that the block error ratio of 2 or more and then, unlike the prototype, masked the entire unit. If N = 0 one of the syndromes are zero, and the other not, then this situation may occur when the block error ratio of 2 or more. It also masked the entire unit. The proposed device is compared with the prototype identifies and masks the entire block, which leads to an additional increase noise immunity, as in the prototype, these situations lead to undetected errors.

When the number of erase N > 3 the device as a prototype, a copy of the flags.

When N = 1 or N = 2, the device as a prototype that produces them. And error values Y1 and Y2 are determined from equations

Y1 = (S1 + S0 * X2)(X1 + X2) ** (-1)

Y2 = (S1 + S0 * X1)(X1 + X2) ** (-1), where S0 and S1 syndromes; X1 and x2 - locators errors (i.e., pomec x2 = 0) Y1 = S1/X1, Y2 = 0.

Fixing one erase may be another situation, when the equation S0 * X1 = S1 fails, i.e., to correct erasing impossible. It is possible in the case when, in addition to one erase block has errors (one or more). While the inventive device in comparison with the prototype (where this situation was not determined), also masks the entire block, which leads to an additional increase noise immunity.

The proposed device is implemented in the form of existing layout that you have the test protocols (see research and Development of the codec correcting reed-Solomon code for high-speed videotrack Studio digital video recorder. Final report on the subject 052-89-09 performed under contract with the Spa (scientific production Association, state reg. N 018900 38301, LEIS, 1990), confirming the efficiency of the device. The device is implemented on the chip C and K series (C. N. Shyla. Popular digital circuits. The Handbook. M. : Radio and communication, 1987).

Diagram of the inventive device in comparison with the prototype provides additional discovery in block errors ratio of 2 or more, which greatly increases the immunity.

In addition to dose used three syndrome (S0, S1, S2) and, therefore, three check bytes, this problem, i.e., the correction of the two erase one or errors, as well as additional discovery is still part of the error ratio of 2 or more (which did not provide a prototype), solved using two check bytes (two syndromes S0 and S1), which is more efficient. (56) USSR Author's certificate N 1332539, CL H 03 M 13/00, 1987.

USSR author's certificate N 1332532, CL H 03 M 13/00, 1987.

The DEVICE FOR DECODING REED - SOLOMON CODE, containing the unit for computing the syndromes and the buffer tank, the inputs of which are combined and an information input device, a control input which is the input of the erase counter, the first synchronization input is the input synchronization unit calculating syndromes, buffer storage and erase counter, a second input synchronization - second input synchronization unit calculating syndromes and erase counter, the output buffer memory connected to the first input of the adders, the output of which is an information output device, and a block of keys, wherein, to improve the noise immunity of the device, it introduced an indication unit single errors, the block OR formirovaniya mask and block repair erase moreover, the control input device connected to the first input unit storing a value s, the second input is combined with the third managing input erase counter, first managing unit display a single error and connected to the first output unit repair erase the first and second inputs which are combined with the corresponding inputs of the indication unit single errors and connected to respective outputs of the computing unit syndromes, the third input is combined with the third input of the display unit single errors and is connected to the output of the erase counter, and a fourth input coupled to the output unit storing a value of erase the first output unit repair erase connected to the first input of the block forming the mask, the second input is connected to the first output unit display a single error, the second output of which is connected to the first input of the unit key, the second input is connected to the output of the unit for computing the error locator and the third input is combined with the first input of the unit for computing the error locator and is connected to the output unit storing a value of the syndrome, whose input is connected to the first output of the computing unit syndromes, and the second whoisprivacy erase connected to the first input of the block OR a second input connected to the output of block keys, and the output connected to the second input of the adders and the output processing unit mask is a control output devices.

 

Same patents:

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

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!