Method for decoding cyclic interference-resistant code

FIELD: communications engineering, in particular, engineering of data transfer systems for decoding cyclic interference-resistant codes without preliminary phasing.

SUBSTANCE: during decoding of cyclic interference-resistant code, range of presumed lengths of code combinations [nmin-nmax] is determined, and assumed phase of beginning of code combination f is set, from phase f in received code series several presumed code combinations Si are selected and pairs are formed from selected combinations in accordance to condition Si≠Sk, N of greatest common divisors, represented by polynomials, is calculated, and from calculated polynomials a polynomial of least order is selected, which is considered equal to original polynomial g(x) of cyclic interference-resistant code, if N of greatest common divisors is equal to "1", then length of proposed code combination n is increased by one, phase of proposed beginning of code combination is altered for one, if greatest common divisor, different from "1", is not found for all n∈[nmin-nmax], combinations of errors are determined in code word and selected code combinations are decoded.

EFFECT: development of method for decoding cyclic interference-resistant code under conditions of adaptation of interference-resistant code to quality of information transfer channel.

3 cl

 

The invention relates to the field of communication technology, in particular to the processing of digital information, and can be used in a wide class of data transmission systems for decoding cyclic error-correcting codes without prior phasing.

The claimed technical solution expands the Arsenal of tools similar purpose due to the possibility of decoding of cyclic error-correcting codes with variable parameters.

There is a method of decoding a cyclic code [Clark J. ml, Kane, J. Encoding with error correction in digital communication systems: Per. s angl. - M.: Radio and communication, 1987. SS-190], which in the first phase of the received code combination, described by the polynomial S(x)is divided by the known generating polynomial g(x). Then calculated and analyzed modulo r(x). If the remainder r(x)=0, then the received code combination is undistorted. If the remainder r(x)≠0, then the received code combination is erased and a signal is generated "error".

The disadvantage of this method is something that happens only error detection without further correction.

Also there is a method of decoding implemented in the device decoding binary cyclic code [USSR author's certificate No. 1339901, CL H 03 M 13/02. The device for decoding docn the th cyclic code. / Svetsaren, Etherington and Nasuhanova registered 23.09.87], in which the first stage determines the components of the syndrome and calculate the syndrome polynomial. Using the obtained data, solve the key equation, determine the polynomial of the error locator and the position of the erroneous character.

This method has low immunity due to the low probability of correct synchronization.

Closest to the claimed method is (prototype) decoding of cyclic error-correcting code [RF patent 2231216 / Method of decoding a cyclic error correcting code / Kvashennikov VI / published 10.02.2004], namely, that on the transmitting and the receiving side pre-set the parameters of cyclic error-correcting (n, k) code, such as the length of the code combination (n), the number of information symbols (k) and a check polynomial h(x), as well as synchronizing sequence on the transmitting side encodes the information sequence cyclic error-correcting code with the given parameters, recurrently continue code word cyclic error-correcting code of length n1>n and form the output sequence representing the sum modulo two of cyclic error-correcting code and a synchronization sequence at the receiving side does not form a cyclic continuation of the received sequence, multiply adopted consistency check on the well-known polynomial error-correcting code h(x) and compute the synchronization sequence, recognize a unique combination of the synchronizing sequence and determine the beginning of the combination of error-correcting code, subtract the synchronization sequence from the received sequence and the received code word cyclic error-correcting code, determines a combination of errors in the code word and correct errors in the information part of the codeword of a cyclic error-correcting code.

This method potentially has high noise immunity, and also carries out cyclic synchronization of cyclic error-correcting code with no additional synchronization symbols, using the redundancy of the error-correcting code.

However, the disadvantage of the prototype is the loss of its capacity in case of change of parameters of error-correcting code in systems with adaptation according to the method of error-correcting coding. Due to the fact that during the implementation of the method requires knowledge of the parameters used error-correcting code, and in systems with adaptation according to the method of error-correcting coding parameters used by the code can be changed.

The purpose of the claimed technical solution is the I development of a method of decoding a cyclic error correcting code, able to survive when it is used in systems with adaptation according to the method of error-correcting coding without additional settings used error-correcting code, due to their definitions directly from the received code sequence before decoding.

This goal is achieved by the fact that in the proposed method of decoding a cyclic error correcting code on the transmission side set the parameters of cyclic error-correcting (n, k) code, such as the length of the code n, the number of information symbols k and the generating polynomial g(x), encode the information sequence cyclic error-correcting code with the given parameters and transmit the generated sequence over the communication channel to the receiving side. At the receiving side define the likely range of lengths code combinations [nmin-nmax] and choose the estimated phase of the start code f. With phase f in the received code sequence identified several alleged code combinations Siand form of the selected combinations of pairs of code combinations according to the condition Si≠Sk. Calculate the N greatest common divisor (GCD), represented by polynomials, for different pairs of code combinations and choose among in the numerical polynomials, which of NOD, the polynomial of least degree that has been associated with a generating polynomial g(x) cyclic error-correcting code. If the GCD is equal to "1", increase the length of the proposed code combinations of n per unit. Change the phase of a proposed start code combination by one if the greatest common divisor other than "1", is not found at all n∈[nmin-nmax]. Determine the combination of errors in the code word and decode the selected code combination.

Thanks to the new essential features in the proposed method will be able to define the parameters used error-correcting code directly from the received code sequence before decoding, which allows the method to survive in case of change of parameters of error-correcting code in systems with adaptation according to the method of error-correcting coding without additional transmission parameters of error-correcting code. In addition, the claimed method allows synchronization code sequence without additional transmission of synchronizing symbols.

The analysis of the level of technology has allowed to establish that the analogues, characterized by a set of characteristics is identical for all features of the claimed technical solution is available, which indicates compliance of the claimed method the condition of patentability "novelty". Search results known solutions in this and related areas of technology in order to identify characteristics that match the distinctive features of the prototype of the features of the declared object, showed that they do not follow explicitly from the prior art. The prior art also revealed no known effect provided the essential features of the claimed invention transformations on the achievement of the technical result. Therefore, the claimed invention meets the condition of patentability "inventive step".

The claimed method can be implemented as follows.

Decoding of cyclic error-correcting code is based on theory of error-correcting coding [Blahut RE Theory and practice codes, controlling errors: TRANS. from English. - M.: Mir, 1986. - 576 C.] and can be set to detect or correct errors.

The basis for the implementation of both regimes are conversion of the received code cyclic error-correcting code with generating or check polynomial that presupposes knowledge of the parameters of cyclic error-correcting code.

In modern conditions the complex electromagnetic environment increases the proportion of systems with adaptation according to the method of error-correcting coding, in which a preference is Agueda the possibility of changing the parameters of error-correcting code depending on the quality of the transmission channel information. In such systems to implement decoding at each change of parameters of error-correcting code is necessary to carry out the transfer on the receiving side, which in turn requires the allocation for these purposes, part of the resource channel information transfer, and also imposes additional requirements on noise immunity when passing parameters of error-correcting code.

To resolve the existing contradictions in the face of changing parameters of cyclic error-correcting code in the process of information transfer is proposed to use the method of decoding of cyclic error-correcting code with a preliminary determination of its parameters directly from the received code sequence.

The essence of the proposed method is as follows.

On the transmission side form the information sequence and set the parameters of cyclic error-correcting code. Next, encode the generated information sequence cyclic error-correcting code with the given parameters and transmit the received code sequence over the communication channel to the receiving side.

At the receiving side define the likely range of lengths code combinations [nmin-nmax]. In the received code sequence specify the estimated phase n the first code combination f nchoose the length of the code n=nminand there are several code combinations Si, i=1,2,..., length n with phase fn.

Of the selected code combinations form pairs according to the condition Si≠Sj, j=1,2,... and i≠j. For selected pairs of code combinations calculate the greatest common divisor (GCD). The GCD computation is performed using the Euclidean algorithm is an iterative algorithm division, the essence of which consists in the following.

If the degree of the polynomial describing the code combination S1greater than or equal to the degree of the polynomial describing the code combination S2the sequence of calculations is

Process is stopped as soon as the result is a balance of zero.

Thus, it is necessary first code combination S1(dividend) divided by the second code combination S2(the divisor) and get the remainder of r1. Then the divisor used in the first stage (the dividend in the second stage), it is necessary to divide the obtained in the first stage, the remainder r1(the divider at the second stage). The process is repeated to obtain a zero balance, with GCD equal to the divisor rnin which turned out to be a zero balance.

After calculation of the N NODES among them choose the one that not only is the h-polynomial of least degree, and identify it with a generating polynomial of the cyclic error-correcting code.

In order to minimize operations calculation number N greatest common divisors believe is equal to 2, which implies the presence of three code words of cyclic error-correcting code. At the first stage search two greatest common divisors GCD1and NOD2. Finding greatest common divisor GCD1and NOD2in the second stage yields a generating polynomial g(x).

Case when GCD is equal to one indicates no common divisor selected code combinations. During this exercise, select the next length code combination n=nmin+1 from a specified range and repeat the process of finding the GCD.

If you are searching all possible lengths of the code combinations of the specified range n∈[nmin-nmax] GCD is not detected, then slip the estimated phase of the start code in the received code sequence and search the NOD for the new phase f=fH+1.

The range of phase change of the beginning of the proposed code combination is determined by the expression f∈[fHfH+nmax].

To improve noise immunity, in the case of errors in the received code sequence, the decision about the truth of generating many is a member of g(x) accept the majoritarian why search for g(x) on different parts of the received code sequence.

Achievable technical result of the proposed method is its application in systems with adaptation according to the method of error-correcting coding, namely in terms of possible changes of the parameters of cyclic error-correcting code.

1. The method of decoding of cyclic error-correcting code, namely, that the pre on the transmission side form the information sequence and set the parameters of cyclic error-correcting code, including the length of the code n, the number of information symbols k and the generating polynomial g(x), which encode the information sequence and transmit it over the communication channel at the receiving side, take a transmitted encoded information sequence, determine the beginning of the code combinations of cyclic error-correcting code and combination error code combination, then decode the selected code combination, characterized in that on the transmission side, the combination of cyclic error-correcting code bkis formed by the multiplication of the information sequence akby the generating polynomial g(x), and on the receiving side before decoding determine product is non polynomial of the cyclic error-correcting code, why specify the range of the assumed lengths of code combinations [nmin-nmax]choose the estimated phase of the start code f, isolated from the accepted encoded information sequence several alleged code combinations Siwhere i=1,2,..., choose from among the selected code combinations of N pairs of code combinations that satisfy the condition Si≠Sjwhere j=1,2,... and i≠j, for each pair of code combinations calculate greatest common divisor, and if the greatest common divisor of these N pairs of code combinations is equal to one, then increase the expected length code combination unit, and repeat the process of finding greatest common divisors, if the enumeration of all possible lengths of the code combinations of the specified range [nmin-nmax] the greatest common divisor other than one that is not found, change the estimated phase of the beginning of the code combination unit and search N greatest common divisors of a new phase in the beginning of the code combination, then of polynomials, which is the greatest common divisors, choose the polynomial of least degree, and identify it with a generating polynomial of the cyclic error-correcting code g(x), and search the generating polynomial g(x) at different phase is x implementation and the decision about the truth of the generating polynomial take on the majority principle.

2. The method according to claim 1, wherein computing the greatest common divisor is performed using the Euclidean algorithm.

3. The method according to claim 1, characterized in that the number N greatest common divisor is chosen equal to two.



 

Same patents:

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: 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

The invention relates to the field of communication technology and can be used in data transmission systems, systems, telemetering and telecontrol

The invention relates to a coder/decoder in a communication system, and more particularly to a device for encoding/decoding of linear block codes by analyzing serial concatenated codes

FIELD: computer science.

SUBSTANCE: device contains commutation level and data processing level, commutation level is formed by computing machines for commutation, and processing level is formed by computing machines for processing. In accordance to method, one commutation computing machine periodically sends control signals to other commutation computing machine and in case of absence of control signal from this commutation computing machine during given time period, erratic functioning of this commutation computing machine is detected, after that, commutation computing machine responsible for detecting erratic functioning, starts execution of functions, normally performed by commutation computing machine, for which erratic functioning was detected.

EFFECT: realization of method and fault-tolerant computing device, which provides for detection of erratic functioning of commutating processor.

2 cl, 3 dwg

FIELD: technologies for storing data in energy-independent ferroelectric memory with variable selection.

SUBSTANCE: each method includes recording multiple identical copies of data to multiple memory zones, first controlling line is read, containing at least first copy of multiple identical copies of data, read data are repeatedly recorded into the same controlling line, read data are transferred to logical memory control contour, reading of whole next controlling line is performed, containing, at least, next copy of multiple identical copies of aforementioned data, data are recorded into same controlling line, from where aforementioned data were read, data are transferred to logical memory control contour, and operations are repeated further until all identical copies of data are transferred to logical memory control contour, errors in binary code are detected, in case of detection of errors corrected data are repeatedly recorded to memory zones where errors were detected.

EFFECT: possible maintenance of integrity of stored data.

2 cl, 8 dwg

FIELD: computer science, namely, engineering of means for protecting information from unsanctioned access.

SUBSTANCE: one of common means utilized for unsanctioned access to information, transferred via local computing network, is a protocol analyzer. Protocol analyzers are functionally capable of copying all of network traffic, and also network frames, satisfying given filtration criterions. Protocol analyzers are connected to network in the same way as workstations. One thing in particular obstructs counteraction to malicious utilization of protocol analyzers, namely, their passiveness. It is not possible to detect presence of aforementioned device in local area network by software means. Common methods utilized to protect information from unsanctioned access within distribution environment of local area network are mainly based on cryptographic protection of files intended for transferring. Method is based on probing distribution environment of local area network by harmonic signal, recording its phase delay, introduced by legitimate network equipment, which is taken as standard, and further tracking of probing signal phase to detect uneven phase delay, introduced by current configuration of network equipment, relatively to recorded standard configuration with removal of effect from network collision and signaling when equality is not maintained. Phase monitoring of probing signal within distribution environment is performed within frequencies range, unaffecting serviceability of local computing network. As a result, continuous and masked control is provided over all physical connections of network equipment to distribution environment of local computing network to facilitate introduction of organizational and technical measures countering unsanctioned access to information. Proposed invention is directed not towards semantic closure of source information transferred by network services, but towards prevention of the very possibility of intercepting network frames in distribution environment of local computing network as a result of timely detection of unsanctioned connection to distribution environment of network equipment, thus significantly increasing level of information protection from unsanctioned access in local computing network.

EFFECT: improved protection of information from unsanctioned access.

2 cl, 8 dwg

FIELD: automatics and computer science, possible use for engineering highly reliable matrix, conveyer, systolic, vector and other processors.

SUBSTANCE: device has block for selecting maximal continual address, flush block, address selection block, block for selecting minimal continual value, block for generating direction code, routing table, block for correcting direction, block for commutating accessibility signals, block for commutating continual address, adder block, source block of bearing voltages, message buffer block, messages commutation block, OR element, 2 analog-digital converters.

EFFECT: expanded application area of homogeneous environment of processor elements due to insertion of technical means providing transmission of message under conditions of appearing breakdowns of separate modules of homogeneous environment of processor elements and communications between them.

20 dwg

FIELD: data transfer using various noise-immune codes; signal receivers of digital communication systems using noise-immune coding for data transfer.

SUBSTANCE: proposed method for automatic choice of source noise-immune code out of given set of noise-immune codes according to adopted code realization includes calculation of syndromes of adopted code realization (probably including sequence of erasing operations or including sequence of slack solutions) followed by counting number of other-than-zero syndromes for each of noise-immune codes out of given set, source noise-immune code being chosen as that for which this counted number of other-than-zero syndromes is lower than threshold value.

EFFECT: ability of selecting source noise-immune code automatically.

4 cl, 1 dwg

FIELD: engineering of reserved device for discontinuous equipment, possible use for creation of various reserved devices for processing of discontinuous information.

SUBSTANCE: multi-channel adaptive device has M identical channels with control system in each of these, power keys, control block and results block. Control block - digital machine with memory, has direct and reverse connections to all device elements, and also to external information sources, functioning determining reliability level, amount of concurrently operating reserved channels, periodicity of their commutation. Control block has logical assembly, memorization assembly, logical circuit. Results block has M-1 identical comparison circuits and M multi-digit multiplexers. Some of result block outputs are connected to output of device. Control system is a system for inbuilt hardware serviceability control of channels based on checking of excessive codes.

EFFECT: savings of working resource of device while maintaining required functioning reliability level.

3 dwg

FIELD: engineering of controlling and measuring equipment, possible use for engineering, producing, testing and operating of radio-electronic products.

SUBSTANCE: device for analyzing breakdowns has block for controlling gradual breakdowns, block for controlling errors, containing frequency splitter, pulse counters, subtracters, OR element, display element, and control block, containing data selector, pulse counter by module N, clock pulse generator, delay elements, memory cells block, AND elements, OR elements.

EFFECT: expanded class of solved problems and improved trustworthiness of analysis results due to controlling of moments when breakdowns occur as well as their duration, pseudo-parallel processing of controlled parameters.

1 dwg

FIELD: electric engineering, in particular, technology for controlling serviceability of controlling and commutating elements of electric circuits, possible use for controlling state of panels for controlling electro-mechanical devices in form of separate keys or switches, and also key-based information input devices in form of keyboards.

SUBSTANCE: method includes forming a series of testing pulses of current with given amplitude and length, sent to each piezoelectric element of key, value of resulting voltage component variable in stabilized state is measured, result of measurement is compared to given maximal and minimal boundary values.

EFFECT: possible detection in real time scale of breakdowns in form of dents or destruction of piezoelectric element crystal, violation of integrity of contact connections and conductors, both before and during process of information accumulation; increased reliability of keyboard.

FIELD: circular memory technologies.

SUBSTANCE: into memory cell, containing the oldest data record, new data record is placed and then pointer is renewed, while aforementioned pointer has first pointer (P1,P1*) and second pointer (P2,P2*), being excessive relatively to first pointer, each of these pointers has control number in form of additional or reversed code of the same pointer.

EFFECT: development of method and circular memory for reliable recording of pointer.

2 cl, 4 dwg

FIELD: medicine.

SUBSTANCE: device can be used by people with paralyzed upper and lower extremities. Device has power unit electrically connected with coordinate aid, signal processing unit and transmitter with aerial. Coordinate aid has non-conductive rectangular plate, carriage being movable relatively longitudinal axis of plate, paired contact and control key fixed rigidly onto paired contact. The contact is electrically connected with signal processing unit; it is mounted onto carriage for movement of paired contact along carriage. Device is placed inside mouth cavity of a person in such a way that is turned with its control key to end of tongue. Surface of control key has relief. Surface of plate has two resistive fields. Any field is separated to equal parts by electro-conductive strip. First resistive field has at its edges electro-conductive vertical contact areas. Second resistive field has at its ends electro-conductive horizontal contact areas. All contact areas are connected with signal processing unit through conductors. Device is small-sized and convenient at exploitation.

EFFECT: improved efficiency of remote control.

4 cl, 3 dwg

FIELD: computers.

SUBSTANCE: device has commutation block, checked microcontroller, block of read-only memory devices of checked microcontroller, block of operative memory devices, PC, controlling microcontroller, block 7 of serial interface, indication block, commutation block of serial interface, block for forming a signal of starting setting of block for forming ROM addresses, block for forming addresses of Rom of checked microcontroller, block for decoding control signals, data-reading block, RAM recording block, block of memory access constants for checked microcontroller, block for forming addresses of checked microcontroller, block for forming start setting signal for controlling microcontroller, RAM reading block, block for forming RAM addresses and power buses.

EFFECT: higher efficiency.

3 dwg

FIELD: computers.

SUBSTANCE: method includes, on basis of contents of central processor registers, received after processor performs some sort of command, by means of mathematical logical operation, forming certain finite control sum and storing it in memory, and on basis of contents of registers, received before start of execution by said processor of directly next command, certain starting checksum is formed, while if starting checksum mismatches finite checksum, error message is generated, which can be followed by halting of processor operation or blocking of chip board with its removal from circulation.

EFFECT: higher reliability.

2 cl, 2 dwg

FIELD: computer science.

SUBSTANCE: signals from each two bits of code of inputted data are converted to 1 of 4 code, calculations in said code are performed in accordance to operation code, result signals in said code are recorded, recorded signals are inputted into code control device and in case of mismatch error signal is generated and processing result output is blocked.

EFFECT: higher trustworthiness.

1 dwg

FIELD: computer science.

SUBSTANCE: method includes protective mathematical conversion of service data of network frame prior to transfer to environment for transfer of a LAN. To said protective conversion the data is subjected, which is contained in headers of network frames of channel level, and also in headers of all encapsulated network packets and segments. As a result the very possibility of interception is prevented.

EFFECT: higher efficiency.

7 cl, 2 dwg

FIELD: computer science.

SUBSTANCE: in the method, called program prior to execution checks data, sent from calling program directly or indirectly.

EFFECT: higher efficiency.

2 cl, 3 dwg

FIELD: measuring equipment.

SUBSTANCE: in turns, on each device, included in diagnosed block, feeding voltage amplitude is decreased in steps from nominal value Enom to threshold value Ethri with step ΔEn, while on each step of decreasing of amplitude of feeding voltage of device pseudo-random multi-digit code sets are sent to inputs of diagnosed block, consisting of logical zeroes and ones with even possibility of appearance of logical zero or logical one in each digit, received logic levels are recorded on outputs of diagnosed digital block and compared to standard levels, and when error frequency Fc appears, voltage value Ethri is recorded (functioning threshold) for each device and its functioning area is calculated on basis of feeding voltage ΔEpi. Defective (potentially malfunctioning) device is detected on basis of lowest value in functioning area ΔEpi, which is selected on basis of comparison of functioning areas of all devices, included in diagnosed digital block.

EFFECT: higher precision, higher efficiency.

1 dwg

FIELD: computer science.

SUBSTANCE: device additionally includes first and second block for address selection of minimal continual value, block for permission of program transfer receiving, first and second demultiplexer blocks, fatal breakdown detector block, support voltages forming block, first, second, third and fourth range selection blocks, vitality signals separation block, block for determining minimal continual value and block for forming vitality signals.

EFFECT: broader functional capabilities.

20 dwg, 1 tbl

Up!