RU2568320C1 - Method of encoding information with sections of linear recurrent sequences - Google Patents

Abstract

FIELD: radio engineering, communication.

SUBSTANCE: method is based on transformation encoded information into phase ratios of two sections of recurrent sequences at the transmitting side and inverse transformations at the receiving side.

EFFECT: high reliability of transmitting information.

6 dwg

Description

The method of encoding information in segments of linear recurrence sequences is intended for encoding discrete messages and can be used both in synchronous and asynchronous systems for transmitting information over communication channels while maintaining high reliability.

The invention relates to radio engineering, and in particular to methods for encoding discrete information, and is intended for encoding discrete information with high reliability. It is written on the basis of the IPC index H04L 17/00.

In the field of discrete information transmission, there is a problem of developing methods for error-correcting coding of information based on linear recurrence sequences. As an analogue of the method, a device is used for transmitting and receiving discrete information (ed. St. USSR No. 642867, H04L 17/00, publ. 1979).

The disadvantages of this device are the relatively high probability of false decoding, susceptibility to error propagation on communication channels with interference, and the dependence of coding efficiency on noise immunity.

A device for transmitting and receiving discrete information contains on the transmitting side a shift register with a feedback circuit, and on the receiving side there is a first shift register with a feedback circuit, between the input and the corresponding output of which an adder modulo two is included, a second shift register with a feedback circuit , counter and trigger control, as well as on the transmitting side - subtracting counter, decoder, inverter, trigger, coincidence unit, OR element and delay unit, while the outputs of the subtracting counter are connected to the corresponding the inputs of the decoder, the output of which is directly and through the inverter connected to the inputs of the trigger, the output of which is connected through a series-connected coincidence unit and the OR element is connected to the clock input of the shift register with a feedback circuit, the output of which is connected to the input of the delay unit, and on the receiving side, the comparison unit , inverter, delay unit, coincidence unit, OR element, totalizing counter and intermediate storage, while the output of the adder modulo two is connected through the inverter to the counter input of the counter, to the input "Reset" the adder output is modulo two and the counter output is connected through a delay unit; between the outputs of the corresponding bits of the first and second registers and the shift with feedback circuits, a comparison unit is switched on, the output of which is connected to the zero input of the control trigger, to the unit input of which the counter output is connected, and the outputs of the control trigger are connected to the inputs of the totalizing counter directly and through the coincidence unit, the output of which is connected to the corresponding input of the second shift register with a feedback circuit through the OR element, and the outputs of the totalizing counter are connected to the corresponding inputs of the intermediate storage, the comparison unit consists of adders, the inputs of which are connected to a second shift register with a feedback circuit, and to the inputs is the first shift register with a feedback circuit of an OR element and an inverter, except In addition, the drawing shows the inputs of the subtracting counter, the inputs and the coincidence unit, the input of the OR element for supplying "fast" clock pulses, the inputs and the element OR, the inputs of the coincidence unit and the communication channel between the transmitting and receiving sides us.

The objective of the invention is to develop a method for error-correcting coding of discrete information, allowing to transmit information with high reliability.

This problem is solved by the fact that the method of encoding information is based on the conversion of the encoded information into the phase relations of two segments of recurrent sequences (RKP) on transmission and inverse transformations on reception.

The analysis of the prior art made it possible to establish that analogues that are characterized by a set of features identical to all the features of the claimed method for encoding discrete information are absent, which indicates compliance of the invention with the patentability condition of "novelty".

Search results for known solutions in this and related fields of technology in order to identify features that match the distinctive features of the claimed invention from the prototype have shown that they do not follow explicitly from the prior art. The prior art also did not reveal the popularity of the impact provided by the essential features of the claimed invention, the transformations on the achievement of the specified technical result. Therefore, the invention meets the condition of patentability "inventive step".

The claimed method is illustrated by drawings, which show:

FIG. 1 is a diagram of the multiplication of field elements;

FIG. 2 - technical implementation of the module for calculating the state of the PGRS based on a single-cycle multiplier of the elements of the field GF (2 ⁿ );

FIG. 3 - stages of the process of coding information by segments of linear recurrent sequences;

FIG. 4 is a structural diagram of an implemented method;

FIG. 5 is a graph of the probability of false decoding of information on the error coefficient in the communication channel for the prototype;

FIG. 6 is a graph of the probability of false decoding of information on the error coefficient in the communication channel for the prototype.

The implementation of the claimed method of encoding discrete information is as follows.

Each RkP segment carries information on the synchronous conversion of two simple generators on shift registers (PGRS) with the same initial state, having different characteristic polynomials P ₁ (x), P ₂ (x) and the same bit depth n (Fig. 3).

To preserve the synchronization of transformations in the case of the sequential transmission of two RkP segments, the initial states of these PGRS are calculated based on the encoded information, the sequence of transmission of the RkP segments over the channel, their magnitude and the choice of the site in the M-sequence.

To ensure the efficiency of coding information, a section at the end of M-sequences is selected with the value (3 ÷ 5) n ₀₁ ≥N ₁ -m ₁ > n ₀₁ and (3 ÷ 5) n ₀₂ ≥N ₂ -m ₂ > n ₀₂ , where n ₀₁ n ₀₂ and the length of "sliding window" on RkP1 RkP2 and correspondingly, N ₁ = N ₂ = 2 ⁿ -1.

If the RkP1 segment is transmitted first, and the RkP2 segment follows it, then to ensure synchronous processing of the segments by the analyzers at the reception, it is necessary that the segment [N ₁ -m ₁ ; N ₁ -m ₂ ] is selected on RkP1, and the segment [N ₂ - on RkP1 m ₂ ; 0], wherein N ₁ -m ₁ = 2 (N ₂ -m ₂ ).

Information from the source in binary form is written into two multipliers of arbitrary elements of the field GF (2 ⁿ ).

Each of the multipliers performs the operation of calculating the binary combination c ₀ + c ₁ ε + ... + c _n-1 ε ^n-1 obtained from the initial [ a ₀ , a ₁ , a ₂ , ..., a _n-1 ] in one clock cycle of it work so if this combination were shifted in the PRGS for a given number of j cycles. For PGRS1, j ₁ = N ₁ -m ₁ , and for PGRS2, j ₂ = N ₂ -m ₂ .

To implement the calculation of the necessary combination, one arbitrary element ε ⁱ and one constant ε ^j belonging to the field GF (2 ⁿ ) are selected. These field elements are expressed through the left power basis as follows:

ε ⁱ = a ₀ + a ₁ ε + ... + a _n-1 ε ^n-1 , a _i ∈GF (2 ⁿ ),

ε ^j = b ₀ + b ₁ ε + ... + b _k-1 ε ^k-1 , b _j ∈GF (2 ⁿ ),

Then the product of these elements

ε ⁱ * ε ^j = ε ^{i + j} = c ₀ + c ₁ ε + ... + c _n-1 ε ^k-1 , c _i ∈GF (2 ⁿ ),

The calculation process c ₀ + c ₁ ε + ... + c _n-1 ε ^n-1 can be implemented in matrix form as the product of the vector [ a ₀ , a ₁ , a ₂ , ..., a _n-1 ] by the matrix that accompanies F in j-th degree (Fig. 1).

The field element multiplication scheme is shown in FIG. one.

The technical implementation of a calculation module based on a single-cycle multiplier is shown in FIG. 2.

The advantage of this scheme is its speed - it takes only one clock cycle to shift the original combination in the PRGS by a given number of j clock cycles.

Nevertheless, for a PRGS length n, n ² schemes of single-cycle multipliers of elements of the field GF (2 ⁿ ) are necessary. For large n, the PGRS state calculation module must be produced on the basis of an n-clock multiplier of elements of the field GF (2 ⁿ ), which requires 3n memory cells, n matching schemes and n + (ω-2) adders in mod2 for their implementation, where ω is the number of nonzero terms of the polynomial P (x).

To set the encoder operation cycle in transmission, it includes a cyclic frequency driver, which, through the PGRS start-up control device, provides the beginning and end of the transmission of the RkP1 and RkP2 segments with a sequential code in turn.

On reception segments RkP1 RkP2 and simultaneously to the inputs of two analyzers PGRS (APGRS), the processing sequence according to the law characteristic polynomials F ₁ (x) and F ₂ (x) respectively. In the analyzers, the recognition of the accepted sections of the RCP by the error-free "sliding" section occurs (figure 3).

схемой сравнения обнаружится совпадение состояний АПГРС1 и АПГРС2, то через устройство управления выводом информации открывается клапан и обеспечивается считывание информации с АПГРС1 параллельным кодом за один такт в буферный накопитель (БН) приема, осуществляется запуск формирователя цикловой частоты. Первый импульс цикловой частоты устанавливает и подключает входы АПГРС1 и АПГРС2 к КС, на вход ОЛЗ на К тактов записывается логическая "1". Величина ОЛЗ на К тактов определяет допустимое время t_авт автономного поддержания синхронизма декодера с кодером, которое определяется скоростью передачи V_пер, стабильностью опорных генераторов кодера и декодера.If an error-free “sliding window” is highlighted by two APGRS, they are sequentially disconnected from the communication channel, go into offline mode, while maintaining synchronization of information processing, and if over time $$t_c=\frac{N_2-m_2}{V_{PeR}}$$

if the comparison scheme detects the state of APGRS1 and APGRS2, then through the information output control device the valve opens and information is read from the APGRS1 parallel code in one clock cycle to the receive buffer (BN), and the cyclic frequency driver is started. The first pulse of the cyclic frequency sets and connects the inputs APGRS1 and APGRS2 to the CS, the logical "1" is written to the input OLZ on K clocks. The value of OLZ on K clocks determines the allowable time _taut autonomous maintaining synchronism of the decoder with the encoder, which is determined by the transmission speed V _per , the stability of the reference generators of the encoder and decoder.

If the next block of information is successfully received within t _avt , then the logical “1” in the OLZ will be deleted for K clocks, and a new “1” will be written to its input with the next pulse of the cyclic frequency from the cyclic frequency former.

If the next block of information is not received within t _avt , then from the OLZ output to K clocks, logical "1" will stop the generation of the cyclic frequency of reception by the shaper and turn on the APGRS control device.

. По истечении времени ожидания устройство управления АПГРС установит анализаторы в исходное состояние. При выделении "скользящего" окна в АПГРС2 за t_ож выключится устройство управления АПГРС и декодер перейдет в основой режим работы и запустит формирователь цикловой частоты.In this case, when the error-free “sliding window” is highlighted by the first APGRS, the control device APGRS will enter the “standby” mode of allocation of the error-free “sliding window” on the second APGRS during $$t_{\mathrm{about}\mathrm{well}}=\mathrm{1,5}\frac{N_2-m_2-n_{02}}{V_{PeR}}$$

. After the waiting time, the control device APGRS will install the analyzers in the initial state. When selecting the "sliding" window to APGRS2 for t APGRS _standby switch off the control device and the decoder enters basis of mode and starts the cycle frequency generator.

If an error-free "sliding window" is allocated by the second APGRS and the error-free "sliding window" is not selected by the first APGRS, the APGRS control device will immediately return the analyzers to their initial state.

The block diagram of the implemented method is presented in FIG. four.

The advantages of this method of encoding information is:

- high noise immunity, determined by the possibility of choosing the size of the "sliding window", comparable with the length of the PRGS, and the length of the segment of the linear recurrence sequence, allowing to find the necessary relationship between noise immunity and coding efficiency;

- the extremely low probability of receiving false information due to the fact that when processing (decoding) one message on reception during one cycle in the set of allowed combinations there will be only one combination, the appearance of which is expected in a strictly defined time interval and only once. This is explained by the fact that the information block determines the initial state of two PRDGs and such a state can occur in each cycle only once when processing segments of a linear recurrent sequence at a reception;

- the method of encoding information provides self-synchronization in the process of transmitting and receiving information, as well as the possibility of applying this method in both synchronous and asynchronous data transfer systems.

Industrial applicability of the invention is due to the fact that a device that implements the proposed method can be implemented using a modern elemental base, with achievement of the purpose specified in the invention. The claimed method of encoding discrete information provides the transmission of information with high reliability.

The performance of the proposed coding system depends on the probability of correctly selecting error-free "sliding windows" at the reception.

Then the full group of events when decoding information is determined by the expression

P _PDC + P _LDK + P _prs = 1

where P _MAC - the probability of correct decoding of information; R _LDK - the probability of false decoding of information; R _prs - the probability of not receiving (skipping) the decoded information.

Reducing the magnitude of one of the components - P or _SWP P _CP increases the value P _MPC and improve noise immunity encoding systems.

For the developed method, the probability of false decoding of information is defined as

where R _sk.ok is the probability of highlighting a "sliding window", n = n ₀ + m, where n ₀ is the length of the LRR, m is the value of the hit counter.

For the prototype, the probability of false decoding of information is defined as:

P _ldk = 1- (P _sk.ok -N · P _but )

The simulation results are presented in FIG. 5 and 6 in the form of graphs of the dependences of the probabilities of false decoding of information on the error coefficient in the communication channel for the prototype (Fig. 5) and the proposed method (Fig. 6) with n = 7.

Claims (1)

The method of encoding information by segments of linear recurrence sequences is that on the transmitting side, the information coming from the source in binary form is written into two multipliers of arbitrary elements of the field GF (2 ⁿ ), each of which performs the operation of computing the binary combination c ₀ + c ₁ ε + ... + c _k-1 ε ^n-1 obtained from the initial [a ₀ , a ₁ , a ₂ , ..., a _n-1 ] in one clock cycle of its operation, in simple generators on shift registers (PRGS), generation segments of M-sequences of length L ₁ and L _2, respectively, the transmission of the irradiated segments of recurrence sequences (RKP) sequentially into the communication channel (KS), parallel input to the inputs of the analyzers of simple generators on the shift register (APGRS) of the RkP1 and RkP2 segments in which the received RkP segments are recognized by the error-free "sliding" section, sequential disconnection from CS and transfer of APGRS1 and APGRS2 to stand-alone operation in the case of allocation of "sliding" windows, search for coincidence of the states of two APGRS in stand-alone operation, recording information from APGRS1 through an open valve in uferny drive (BN) in the event of coincidence with the starting cyclic reception frequency generator, and connecting APGRS1 APGRS2 for COP for the next processing of incoming RCP segments.

Images