A device for decoding of linear codes

 

(57) Abstract:

The invention relates to computing. The device for decoding linear codes, contains a separation unit symbols and several N identical stages i decode. Information in and check with the outputs of the separation unit symbols are respectively information and testing the inputs of the first stage of decoding. In each stage i decode the information input is connected to the serially connected between an information register, the delay elements and the adder, and the testing input - to consistently related to Raman adder and a verification unit, and a bitwise outputs information register of the first stage associated with combination adder. The test unit consists of a sequence of bitwise and linked syndromic switch, syndromic case and a casting device with the switch, and bit-by-bit outputs of the syndrome register are associated with syndromic switch. The information output of stage i of decoding is output fi adder, a second input connected with the shear output information register. 1 C.p. f-crystals, 5 ill.) - Rev. investing linear codes, and can be used in data transmission systems.

In the transmission signal is distorted by noise and interference, operating in the communication channels. One method of combating this effect is robust encoding. The choice of code depends on the quality of the channel, the required accuracy and feasibility of hardware decoding, which is the most difficult process in the procedure of reception and transmission of information, if you want not only to detect errors but also to correct them.

The coding theory offers a large selection of codes, but the problem is practically impossible complexity of decoding devices when the desired length of the code sequence.

For example, effective enough at the moment are decoders that implement the Viterbi algorithm (AB) and actively used in satellite and space channels in the U.S., Japan and Western Europe. This theoretically optimal algorithm for the error probability, in addition, it provides good results when taken without assessing the reliability and even better when taken with a confidence score.

However, due to the exponential growth I codes allow you to work decoders for concatenated codes (QC). Since these codes have a very large code distance, with a low level of noise they make a very small error probability at the output.

However, when a large noise level of their efficiency is low due to the fact that the code in General actually is decoded by far not optimal. Only when using AB internal code specifications QC will be acceptable reliability, but then the whole QC will have the disadvantages of AB.

It is known device for decoding convolutional (mno,mko) code, consisting of a separation unit of the character information output of which is connected with the information register, and check through the adder connected to the syndrome register. The second input of the adder is connected with the output switch, the inputs of which are formed by the outputs of the adders certain bits of information register. The outputs of syndromic case through logic come on bitwise inputs syndromic case and, being summarized in the course access information register, form the output of the entire device.

However, the device provides a fairly low reliability of the decoding, which limits its use only in channels with discendum threshold of Transenda and Weldona, check block which consists of the syndrome register and the associated through combinational adder majority element, the output of which changes the decoded symbol only when the level of logical units is reached by a certain number of inputs of a majority element, corresponding to the set threshold. When changing the value of the symbol, the syndrome changes and the threshold is incremented. The threshold is decremented by one at the completion of each cycle, stopping decoding, reaching its lowest value.

The device allows you to fix many combinations of errors that are not correctable in the normal decoding in a single step, however, requires much more time, complicating the apparatus and is applicable only to block codes.

A known system for detecting and correcting errors for convolutional codes [2] the decoder which contains the separation unit symbols, one output of which is connected to the Raman adder and sequentially interconnected information register, a delay element and an adder. The second output of the separation unit symbols connected with the serially connected combination of sums of the TRS outputs bitwise associated with combination adder. The input of the separation unit is the input of the decoder system, and the output of the adder output of the entire system.

At the input of decoder symbols distorted by errors in the channel, divided by the separation unit symbols on information and testing, which are received respectively in the information register and through combinational adder in syndromic case, which by the threshold element forms a decision on the reliability of the decoded symbol, reversing it if necessary on the output of the adder.

However, the system works with short codes and long provides a fairly low level of confidence decoding, which imposes restrictions on the allowable interference level in the channel and substantially narrows the scope of the system.

The objective of the invention is to provide such a device for decoding of linear codes, which, while maintaining the ease of implementation, would provide a significant increase in the reliability of the decoding.

This task is solved in that the device for decoding linear codes, including the separation unit symbols, the information output of which is connected with the combination accumulator and consequently the and separation of symbols connected with the serially connected combination adder and a verification unit, and bitwise outputs information register associated with the Raman adder, and the testing unit comprises sequentially and bitwise linked syndromic switch, syndromic case, the switch casting device and a casting device, where bit-by-bit outputs of the syndrome register are associated with syndromic switch, the first input of which is the entrance of a casting device and all of the test unit and the second input is connected with the output of a casting device, which is the output of the test unit, which is connected with the adder and the input of the separation unit symbols is input only device is further provided with at least one step of the decoding, includes a test unit and sequentially connected between a data register, a delay element and an adder, which is connected at the input to the test unit, and the input information register and the input of the test block are the inputs of all stages of decoding, and its outputs are the output of the adder and the shift output of the syndrome register, and the number of steps of the decoding depends on the level of noise in the channel and the output device is output sumatraensis least 100 times.

It is advisable test the additional section to provide sequentially connected between a differential case and a full adder, and the differential input register and the output of the adder are respectively the input and output of the test unit, and the output of the differential case connected to the input of a casting device, the output of which is connected to the second input of the adder.

This allows to increase the reliability of the decoding in 3-10 times.

You may check block to provide additional multipliers for weighting factors that are included, one for each input of a casting device.

This provides an even higher level of reliability of the decoding.

In Fig. 1 shows a block diagram of the device of Fig.2 the simplest structural diagram of the test unit of Fig.3 is a structural diagram of the test unit, the variant of Fig.4 block diagram of the test unit, the variant of Fig.5 block diagram of the implementation of the device option.

The device for decoding linear codes contains the unit 1 division of characters (Fig.1), the input of which is an input only device, and an information output b which is connected with the serially connected between abderemane, and with series connected combination adder 5 and the test block 61the first stage 1 decoding. Check the input unit 1 division of symbols connected with the Raman adder 5, and the bitwise outputs information register 21also connected to the combination adder 5. The output of the d1test unit 61connected to the adder 41exit f1which is an information output stage of the first decoding. Outlet e1test unit 61is the check out stage 1 decoding.

Stage 1 decoding is connected with at least one additional stage II decoding, and information output f1the decode stage I is connected to serially interconnected information register 22element 32delay and adder 42. Check out the e1stage 1 decoding is connected to a test unit 62the output of the d2which is connected to the adder 42and outputs f2adder 42and e2test unit 62are respectively information and testing the outputs of stage II deck is CLASS="ptx2">

Test unit 6 (Fig.2) any stage contains syndromic switch 7, the input g which is the entrance test block 6, and bit-by-bit inputs and outputs syndromic switch 7 are connected respectively with the bitwise outputs and inputs syndromic case 8. Bitwise outputs syndromic case 8, also connected with the switch 9 a casting device, which is connected with the casting device 10, one input of which is the input g of the test block 6, and the output d is connected to the input of syndromic switch 7 and an information output of the test unit 6, and the output e of the last discharge syndrome register 8 is the test output of the test unit 6.

As a combinational adder 5, syndromic switch 7 and switch 9 a casting device used for the intended purpose are widely known logic circuits that implement the required code polynomials.

Crucial device 10 is a device that includes a means of summing the input signals, and comparing the sum with a set threshold value, and generating the output signal when exceeding the results of summation of the threshold value.

Device is correctly received information and check symbols linear code. Unit 1 division of characters they are divided into two flow information b and test C. Information symbols b are filled by lateral inputs information register 21along with the check symbols come in combinational adder 5, which is determined by the difference between the received information b symbols and educated from the received check symbols with which shear inputs fills syndromic case 81test unit 61. Bitwise outputs syndromic case 81enter the switch 91a casting device, and from there to the input of a casting device 101where a signal from input g1test unit 61and where certain bits are summed, and the sum is compared with some threshold value which is set depending on the combination of values of inputs a casting device 101and the excess which forms the decision to change the decoded symbol that occurs on the output of the adder 41stage 1 decoding, which simultaneously receives the signal d1from the output of a casting device 101and an information signal that has passed the element 31delay. This decoded indranil register 82which is transmitted modified in accordance with the output of a casting device 10 is f1the last digit of the previous syndromic case 81. Crucial device 102this second stage decoding based on the set threshold makes its decision d2about the necessity of correction of the decoded symbol, passing the symbol f2and the last category of e2his syndromic case 82in the following degree III decoding, and so forth.

Check block 6 any stage (Fig.3) may further comprise a differential case 11, entrance h which is an additional entrance test unit 6 and the output of which is connected to the input of a casting device 10 and the adder 12, the second input is connected with the output d of the casting device 10. The q output of the adder 12 is an additional entrance test block 6.

Entrance h2the first additional step II decoding is connected to a source of logic level zero, and the output of qNthe last stage of the N decoding is not used.

In this case, the operation of the device (Fig.3) more complicated by the fact that at the input of a casting device 10icomes complement what galom dia casting device 10igenerates a signal qito fill the differential case 11i+1the next stage (i+1)-th decoding.

Check block 6 any stage (Fig.4) may further comprise blocks 13 multiplied by weights placed one at each entrance of a casting device 10.

The operation of the device (Fig.4) in this case differs only in the fact that all input signals of a casting device 10 pass through the blocks 13 multiplied by weighting factors, to account for the different degree of influence of the input symbols on the decision made by the deciding device 10, which in turn increases the reliability of the decoding.

In Fig.5 presents a block diagram of the simplest version of the device run for decoding convolutional codes binary information sequence with the code length limitations 14, code distance of 5, code polynomial 1 + x + x4+ x6and transfer rate 1/2. The device comprises a four-stage decoding. Critical devices are implemented threshold elements that have the thresholds, respectively, 3 3 2 2.

In the adder And develop test symb from the information symbols b, filling in the information register RG21(the key to the position "a"). Their sum, which is mod2will give 0 if there is no distortion in the channel and I if distortion has occurred, arrives in syndromic case RG81the only error checking symbols will cause the unit to the syndrome register RG81at the place corresponding to erroneous test symbol that will lead to the fact that on any of the 13 shifts syndromic RG81(and information RG21) register the amount of units on the threshold element 101will not exceed 1 < 3 and the signal will not be changed.

If an error has occurred in the information symbol, for example in the ninth grade, the syndrome register RG81will receive the filling of the form 0001010011000, which will give the amount of the checks on the threshold element 1014 > 3 only at such position shift registers RG21and RG81when will be decoded symbol corresponding to the ninth digit seeding information register RG21, i.e., inverted on the adder D1will it mistakenly by information symbol.

The first stage decoding provides the probability of error Dec is already theoretically possible values for this code.

Introduction to the scheme of three levels of decoding, where the transmitted status information of the register RG2iand senior level eisyndromic case RG8ipre - ditusa stage i decoding, allows to obtain Rin(e) 10-5.

Introduction to the scheme of differential case (Fig.3) and multipliers for weighting factors (Fig. 4) allows to increase the decoding device to a more powerful codes up to Rin(e) 10-5when Rabout0,056.

Thus, the device for decoding linear codes allows you to correct errors in the digital data via satellite, space, relay and other expensive and high-speed channels, networks, digital high-definition television in the digital videomining record.

The device, which ensures fast and reliable decoding in a wide range of channel parameters and code that implements a near-optimal solution for long-correcting codes.

The device provides performance 10-30 times higher than other types of decoders, and is comparable to the speed of advance information on the shift registers in the selected element basis.

-410-7and less, on average, every character, including telephone networks.

Whole new level of noise immunity is achieved in a particularly simple and homogeneous elements.

The device quite easily realizable in the form of custom and matrix LSI microprocessor circuit boards and software.

1. The DEVICE FOR DECODING LINEAR CODES, including the unit 1 division of characters, the information output b which is connected to the Raman adder 5 and sequentially interconnected information register 21element 31delay and adder 41and check the output c of the unit 1 division of symbols connected with the serially connected combination adder 5 and the test block 61and bitwise outputs information register 21associated with combination adder 5, and the testing unit 61consists of sequentially and bitwise linked syndromic switch 71, syndromic case 81, a casting device 101with the switch 91and bit-by-bit outputs of the syndrome register 81associated with syndromic commutation block 61and the second input is connected with the output of a casting device 101which is the output of the d1test unit 61that is associated with the adder 41and the input a of the unit 1 division of characters is input only device, wherein the device is further provided with at least one degree 11 decode, which includes a test block 62and consistently related information register 22element 32delay and adder 42the input of each of which is connected to a test unit 62to the f1information register 22and the input e1test unit 62connected respectively to the outputs of the adder 41and the test block 61the first stage 1 decoding and are the inputs of all the stages 11 decode, and its outputs are the output of the f2adder 42and shear exit e2syndromic case 82and the number N of stages of the first decoding depends on the required reliability of the decoded signal and the output device is an output of fNadder 4Nthe last stage of the N decoding.

2. The device under item 1, the best of the register 11 and the adder 12, moreover, entrance h differential case 11 and the q output of the adder 12 are respectively input h and the output q of the test block 6, and the output of the differential case 11 is connected to the input of a casting device 10, the output d of which is connected to the second input of the adder 12.

 

Same patents:

Encoder // 2033691
The invention relates to computing

The invention relates to computing and data transmission and can be used to control structural codes

The invention relates to computing and communications

The invention relates to a device for the transmission of discrete data and can be used in systems of automatic locomotive alarm, Autolock and other devices of railway automatics

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

The invention relates to computing and communication technology and can be used in digital communication systems using convolutional codes

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 invention relates to telecommunications and is intended for use in digital transmission systems convolutional code

The invention relates to computer technology and can be used in communication systems and information processing, operating with modular codes

The invention relates to computing and communication technology in the information transmission codes JUICE and can be used in computing devices operating in JUICE

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!