[go: up one dir, main page]

RU2743854C1 - Binary equivalent code combination generator - Google Patents

Binary equivalent code combination generator Download PDF

Info

Publication number
RU2743854C1
RU2743854C1 RU2019140308A RU2019140308A RU2743854C1 RU 2743854 C1 RU2743854 C1 RU 2743854C1 RU 2019140308 A RU2019140308 A RU 2019140308A RU 2019140308 A RU2019140308 A RU 2019140308A RU 2743854 C1 RU2743854 C1 RU 2743854C1
Authority
RU
Russia
Prior art keywords
block
output
input
permutations
decisions
Prior art date
Application number
RU2019140308A
Other languages
Russian (ru)
Inventor
Анатолий Афанасьевич Гладких
Басем Абдулсалам Салех Саид
Анастасия Денисовна Бакурова
Original Assignee
федеральное государственное бюджетное образовательное учреждение высшего образования "Ульяновский государственный технический университет"
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by федеральное государственное бюджетное образовательное учреждение высшего образования "Ульяновский государственный технический университет" filed Critical федеральное государственное бюджетное образовательное учреждение высшего образования "Ульяновский государственный технический университет"
Priority to RU2019140308A priority Critical patent/RU2743854C1/en
Application granted granted Critical
Publication of RU2743854C1 publication Critical patent/RU2743854C1/en

Links

Images

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/27—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques
    • H03M13/2703—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques the interleaver involving at least two directions
    • H03M13/271—Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column permutations
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2942—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes wherein a block of parity bits is computed only from combined information bits or only from parity bits, e.g. a second block of parity bits is computed from a first block of parity bits obtained by systematic encoding of a block of information bits, or a block of parity bits is obtained by an XOR combination of sub-blocks of information bits
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/3784—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35 for soft-output decoding of block codes

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)

Abstract

FIELD: electrical communication engineering.
SUBSTANCE: invention refers to communication engineering. Generator allows neutralizing the negative effect of unproductive permutations with minimum time losses due to the purposeful transformation of the unsuccessful permutation. This is facilitated by a divided cognitive map of the generator, when using this method, the question of whether the current permutation belongs to negative solutions and the transformation of such a permutation is solved first. Smaller portion of such permutations facilitates more efficient generation of combinations of binary equivalent codes. Productivity of the generator is significantly improved by excluding matrix calculations from the data processing algorithm.
EFFECT: technical result consists in reduction of cycle of generation of combinations of required equivalent codes and in reduction of volume of memory required for storage of reference matrices of equivalent codes.
1 cl, 1 dwg

Description

Изобретение относится к технике связи и может использоваться при проектировании новых и модернизации существующих систем обмена данными.The invention relates to communications technology and can be used in the design of new and modernization of existing data exchange systems.

Заявленное устройство расширяет арсенал мягкого декодирования двоичных избыточных блоковых кодов за счет исправления доли стираний, кратность которых выходит за пределы минимального кодового расстояния. Для этого используются известные свойства эквивалентных кодов (см. У. Питерсон, Э. Уэлдон. Коды, исправляющие ошибки. Ред. Р.Л. Добрушин и СИ. Самойленко. М.: Мир, 1976. - С. 76-78). Для двоичных кодов реализация подобных свойств может иметь как положительный, так и отрицательный исход, который зависит от конфигурации перестановок принятых символов на длине кодового вектора в зависимости от текущих значений мягких решений. Положительный результат формируется в том случае, когда выполненная по результатам оценки мягких решений перестановка символов принятой кодовой комбинации не приводит к линейной зависимости столбцов, адекватно переставленной порождающей матрицы кода. В противном случае формирование эквивалентного кода положительного результата не дает. Как правило, количество положительных решений, из общего множества возможных решений, составляет большую его часть (см. Гладких А.А. Перестановочное декодирование как инструмент повышения энергетической эффективности систем обмена данными / Электросвязь №8. - 2017. - С 52-56).The claimed device expands the arsenal of soft decoding of binary redundant block codes by correcting the proportion of erasures, the multiplicity of which is beyond the minimum code distance. For this, the well-known properties of equivalent codes are used (see W. Peterson, E. Weldon. Error-correcting codes. Ed. RL Dobrushin and SI Samoilenko. M .: Mir, 1976. - P. 76-78). For binary codes, the implementation of such properties can have both a positive and a negative outcome, which depends on the configuration of the permutations of the received symbols over the length of the code vector, depending on the current values of soft decisions. A positive result is formed in the case when the permutation of the symbols of the received codeword, performed according to the results of the soft decision evaluation, does not lead to a linear dependence of the columns of the adequately permuted generating matrix of the code. Otherwise, the formation of an equivalent code does not give a positive result. As a rule, the number of positive decisions, out of the total set of possible solutions, makes up most of it (see A. Gladkikh, Permutation decoding as a tool for increasing the energy efficiency of data exchange systems / Electrosvyaz No. 8. - 2017. - P 52-56).

Известно также устройство - Декодер с упорядоченной статистикой символов (см. патент РФ 2490804), в котором частично решается задача запоминания тех комбинаций номеров переставленных столбцов порождающей матрицы основного кода, определитель которых указывает на вырожденность переставленных матриц и невозможность реализовать декодирование с использованием эквивалентного кода. Следовательно, для невырожденных матриц процедура поиска переставленных порождающих матриц и приведение их к систематической форме для получения эквивалентного кода выполняется в декодере даже в том случае, если образец переставленного вектора уже обрабатывался декодером.There is also known a device - a Decoder with ordered statistics of symbols (see RF patent 2490804), which partially solves the problem of memorizing those combinations of numbers of rearranged columns of the generating matrix of the basic code, the determinant of which indicates the degeneracy of the rearranged matrices and the impossibility of decoding using an equivalent code. Therefore, for non-degenerate matrices, the procedure for searching for permuted generating matrices and reducing them to a systematic form to obtain an equivalent code is performed in the decoder even if the sample of the permuted vector has already been processed by the decoder.

Известно также устройство - декодер с повышенной корректирующей способностью (см. патент РФ 2438252), которое практически реализует способ, описанный в работе Р. Морелос-Сарагосы с незначительным уточнением процедуры получения МРС. В таком декодере, по сути, сохраняются все недостатки, характерные для решений по патентам 2444127, 2490804 и 2580797.It is also known a device - a decoder with an increased correcting ability (see RF patent 2438252), which practically implements the method described in the work of R. Morelos-Zaragoza with a slight refinement of the procedure for obtaining MRS. In such a decoder, in fact, all the disadvantages characteristic of solutions for patents 2444127, 2490804 and 2580797 are preserved.

Близким по технической сущности заявленному генератору комбинаций двоичного эквивалентного кода является перестановочный декодер с режимом обучения по патенту №2644507, когда перестановочный декодер с режимом обучения, содержащем блок приема, первый выход которого через последовательно включенные блок мягких решений символов и накопитель оценок, подключен к входу блока упорядочения оценок, при этом первый выход накопителя кодовой комбинации подключен к первому входу блока эквивалентного кода, один выход которого подключен к первому входу блока контроля линейности, второй выход которого подключен ко второму входу блока эквивалентного кода, другой выход которого подключен к первому входу блока сравнения и обратных перестановок, выход которого подключен ко второму входу блока исправления стираний, тогда как его первый вход подключен ко второму выходу накопителя кодовой комбинации, дополнительно введены датчик последовательностей столбцов, переключатель режимов, блок отрицательных решений, блок положительных решений и детектор режимов, вход которого подключен ко второму выходу блока приема, при этом первый выход детектора режимов подключен к входу накопителя кодовой комбинации, а второй выход детектора режимов через датчик последовательностей столбцов подключен к одному входу переключателя режимов, другой вход которого подключен к выходу блока упорядочения оценок, при этом первый выход блока контроля линейности подключен к входу блока отрицательных решений, а выход этого блока соединен со вторым входом блока контроля линейности, тогда как третий выход блока контроля линейности через блок положительных решений подключен ко второму входу блока сравнения и обратных перестановок, при этом выход переключателя режимов подключен к третьему входу блока эквивалентного кода.Close in technical essence to the claimed generator of combinations of a binary equivalent code is a permutation decoder with a learning mode according to patent No. 2644507, when a permutation decoder with a learning mode containing a receiving unit, the first output of which is connected to the input of the unit through a series-connected block of soft symbol decisions and an accumulator of estimates ordering the estimates, while the first output of the code combination drive is connected to the first input of the equivalent code block, one output of which is connected to the first input of the linearity control unit, the second output of which is connected to the second input of the equivalent code block, the other output of which is connected to the first input of the comparison block, and reverse permutations, the output of which is connected to the second input of the erasure correction unit, while its first input is connected to the second output of the code combination drive, a column sequence sensor, a mode switch, a block of negative decisions are additionally introduced, block of positive decisions and a mode detector, the input of which is connected to the second output of the receiving unit, while the first output of the mode detector is connected to the input of the code combination storage, and the second output of the mode detector through the column sequence sensor is connected to one input of the mode switch, the other input of which is connected to the output of the evaluation ordering unit, while the first output of the linearity control unit is connected to the input of the negative decision block, and the output of this block is connected to the second input of the linearity control unit, while the third output of the linearity control unit is connected through the positive decision block to the second input of the comparison and reverse permutations, while the output of the mode switch is connected to the third input of the block of the equivalent code.

Достоинством прототипа является возможность закреплять в памяти декодера результаты поиска порождающих матриц эквивалентных кодов для формируемых перестановок и использовать эти результаты при повторении перестановок, не прибегая к сложным матричным вычислениям.The advantage of the prototype is the ability to fix in the decoder's memory the search results for generating matrices of equivalent codes for the generated permutations and use these results when repeating permutations without resorting to complex matrix calculations.

Недостатками прототипа являются: во-первых, большой объем памяти для хранения полученных результатов из-за недостаточной ее организации по причине не использования циклических свойств кодов; во-вторых, знание порождающей матрицы эквивалентного кода не исключает матричных вычислений необходимых для поиска вектора эквивалентного кода, что отрицательно сказывается на сложности реализации перестановочного декодера; в-третьих, появление перестановок, приводящих к вырожденным матрицам, отрицательно сказывается на процедуре синхронизации кодеков из-за неопределенности времени поиска новых подходящих перестановок символов на приемной стороне.The disadvantages of the prototype are: firstly, a large amount of memory for storing the results obtained due to its insufficient organization due to the non-use of the cyclic properties of the codes; secondly, knowledge of the generating matrix of the equivalent code does not exclude the matrix computations necessary to find the vector of the equivalent code, which negatively affects the complexity of the implementation of the permutation decoder; thirdly, the appearance of permutations leading to degenerate matrices adversely affects the codec synchronization procedure due to the uncertainty of the search time for new suitable permutations of symbols on the receiving side.

Технический результат при осуществлении изобретения заключается в сокращении цикла генерации комбинаций требуемых эквивалентных кодов и уменьшении объема памяти необходимой для хранения эталонных матриц эквивалентных кодов.The technical result in the implementation of the invention is to shorten the generation cycle of combinations of the required equivalent codes and reduce the amount of memory required for storing the reference matrices of equivalent codes.

Технический результат достигается за счет того, что в предлагаемом генераторе комбинаций двоичного эквивалентного кода, содержащий блок приема, первый выход которого через последовательно включенные блок мягких решений и накопитель оценок подключен к одному входу блока упорядоченных оценок, первый выход которого через блок отрицательных решений и его первый выход подключен к другому входу блока упорядоченных оценок отличающийся тем, что дополнительно введены блок нумераторов, блок когнитивной карты, блок перестановок эталонной матрицы, блок сложения, блок жестких решений, блок информационных разрядов и накопитель комбинации, при этом второй выход блока упорядоченных оценок через блок нумераторов подключен к первому входу блока перестановок эталонной матрицы, а второй вход этого блока через блок когнитивной карты подключен к другому выходу блока отрицательных решений, тогда как выход блока перестановок эталонной матрицы подключен к первому входу блока сложения, выход которого соединен с первым входом накопителя комбинации, при этом второй вход этого блока подключен к другому выходу блока информационных разрядов, первый выход которого подключен к второму входу блока сложения, а третий выход блока упорядоченных оценок через блок жестких решений подключен к входу блока информационных разрядов.The technical result is achieved due to the fact that in the proposed generator of combinations of a binary equivalent code, containing a receiving unit, the first output of which is through a series-connected block of soft decisions and an accumulator of estimates is connected to one input of the block of ordered estimates, the first output of which is through the block of negative decisions and its first the output is connected to another input of the block of ordered evaluations, characterized in that a block of enumerators, a block of a cognitive map, a block of permutations of a reference matrix, an addition block, a block of hard decisions, a block of information bits and a combination accumulator are additionally introduced, while the second output of the block of ordered evaluations through the block of enumerators is connected to the first input of the block of permutations of the reference matrix, and the second input of this block through the block of the cognitive map is connected to another output of the block of negative decisions, while the output of the block of permutations of the reference matrix is connected to the first input of the addition block, the output of which is connected to the first input of the combination accumulator, while the second input of this block is connected to another output of the block of information bits, the first output of which is connected to the second input of the addition block, and the third output of the block of ordered estimates through the block of hard decisions is connected to the input of the block of information bits.

Структурная схема генератора комбинаций двоичного эквивалентного кода представлена на фигуре, где:The block diagram of the generator of combinations of a binary equivalent code is shown in the figure, where:

1 - блок приема;1 - receiving unit;

2 - блок мягких решений;2 - block of soft decisions;

3 - накопитель оценок;3 - rating accumulator;

4 - блок упорядоченных оценок;4 - a block of ordered assessments;

5 - блок отрицательных решений;5 - block of negative decisions;

6 - блок нумераторов;6 - block of numerators;

7 - блок когнитивной карты;7 - block of a cognitive map;

8 - блок перестановок эталонной матрицы;8 - block of permutations of the reference matrix;

9 - блок сложения;9 - addition block;

10 - блок жестких решений;10 - block of hard decisions;

11 - блок информационных разрядов;11 - block of information bits;

12 - накопитель комбинации.12 - combination accumulator.

Генератор комбинаций двоичного эквивалентного кода, содержит блок приема 1, первый выход которого через последовательно включенные блок мягких решений 2 и накопитель оценок 3 подключен к одному входу блока упорядоченных оценок 4, первый выход которого через блок отрицательных решений 5 и его первый выход подключен к другому входу блока упорядоченных оценок 4 при этом второй выход блока упорядоченных оценок 4 через блок нумераторов 6 подключен к первому входу блока перестановок эталонной матрицы 8, а второй вход этого блока через блок когнитивной карты 7 подключен к другому выходу блока отрицательных решений 5, тогда как выход блока перестановок эталонной матрицы 8 подключен к первому входу блока сложения 9, выход которого соединен с первым входом накопителя комбинации 1, при этом второй вход этого блока подключен к другому выходу блока информационных разрядов 11, первый выход которого подключен к второму входу блока сложения 9, а третий выход блока упорядоченных оценок 4 через блок жестких решений 10 подключен к входу блока информационных разрядов 11.The generator of combinations of a binary equivalent code, contains a receiving unit 1, the first output of which is connected to one input of the block of ordered estimates 4, the first output of which is through the block of negative decisions 5 and its first output, through the block of negative decisions 2 and the accumulator of estimates 3, to another input block of ordered estimates 4, in this case, the second output of the block of ordered estimates 4 through the block of enumerators 6 is connected to the first input of the block of permutations of the reference matrix 8, and the second input of this block through the block of cognitive map 7 is connected to another output of the block of negative decisions 5, while the output of the block of permutations the reference matrix 8 is connected to the first input of the addition block 9, the output of which is connected to the first input of the combination drive 1, while the second input of this block is connected to the other output of the block of information bits 11, the first output of which is connected to the second input of the addition block 9, and the third output block of ordered evaluations 4 through block tikh decisions 10 is connected to the input of the block of information bits 11.

Вход блока приема 1 является общим входом генератора комбинаций двоичного эквивалентного кода, а выход накопителя комбинаций 12 является общим выходом устройства.The input of the receiving unit 1 is the common input of the generator of combinations of the binary equivalent code, and the output of the accumulator of combinations 12 is the common output of the device.

Работу предлагаемого устройства рассмотрим на примере кода Хэмминга (7, 4, 3) с порождающей матрицей G видаLet us consider the operation of the proposed device using the example of the Hamming code (7, 4, 3) with a generating matrix G of the form

Figure 00000001
Figure 00000001

Столбцы матрицы G нумеруются от 1 до 7 слева направо в виде верхних индексов (нумераторов) у символов верхней строки этой матрицы. Пусть источник информации передает информационный вектор Vинф=1010, тогда в канал связи будет отправлен вектор Vкан=Vинф×G=1010011. Пусть вектор ошибок Vе при передаче по каналу связи вектора Vкан имел вид Ve=0011010. Тогда в ходе фиксации вектора приема Vпp=Vкан⊕Ve в блоке приема 1 и последовательной выработки для каждого бита этого вектора мягких решений в блоке мягких решений2 формируется совместная последовательность жестких решений символов и соответствующих им целочисленных МРС. В результате в накопителе оценок 3 фиксируется вектор вида:The columns of the matrix G are numbered from 1 to 7 from left to right in the form of superscripts (numerators) at the symbols of the top row of this matrix. Let the information source transmit the information vector V inf = 1010, then the vector V kan = V inf × G = 1010011 will be sent to the communication channel. Let V error vector e for transmission over the communication channel ch vector V has the form V e = 0,011,010. Then, during the fixation of the reception vector V p = V kan ⊕V e in the reception block 1 and sequential generation for each bit of this soft decision vector in the soft decision block 2, a joint sequence of hard decisions of symbols and corresponding integer MPCs is formed. As a result, a vector of the form is fixed in the accumulator of estimates 3:

Figure 00000002
Figure 00000002

Последовательность МРС в блоке мягких решений 2 формируется по правилу

Figure 00000003
где ρ - интервал стирания; Ев - энергия сигнала, приходящаяся на один информационный бит; Zi - уровень принятого сигнала (модулируемого параметра); λmax - фиксированная целочисленная оценка МРС с максимальным значением, как правило, определяемая конструктором декодера(см. А.А. Гладких. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи, Ульяновск. - 2010 с. 211). Пусть λmax=7. В блоке упорядоченных оценок 4 после перестановок жестких решений по убыванию ихThe MPC sequence in soft decision block 2 is formed according to the rule
Figure 00000003
where ρ is the erasure interval; E in - signal energy per one information bit; Z i - the level of the received signal (modulated parameter); λ max is a fixed integer estimate of the MPC with a maximum value, as a rule, determined by the decoder constructor (see A.A. Gladkikh. Fundamentals of the theory of soft decoding of redundant codes in an erasing communication channel, Ulyanovsk. - 2010 p. 211). Let λ max = 7. In the block of ordered estimates 4, after permutations of rigid solutions in decreasing order, their

МРС вектор Vмpc преобразуется к виду:MRS vector V mpc is converted to the form:

Figure 00000004
Figure 00000004

Блок упорядоченных оценок 4 выделяет из переставленного вектора Vпpc нумераторы первых k символов, формируя последовательность 1 7 2 5, которая затем приводится к упорядоченному виду: 1 7 2 5

Figure 00000005
1 2 5 7. Упорядоченная последовательность 1 2 5 7 направляется в блок отрицательных решений 5, где лексикографически сравнивается с образцами запрещенных перестановок, приводящих к формированию вырожденных матриц, что однозначно не позволяет получить эквивалентный код. Перечень таких перестановок для кода (7, 4, 3) приведен в таблице 1.The block of ordered estimates 4 extracts the enumerators of the first k symbols from the permuted vector V npc , forming the sequence 1 7 2 5, which is then reduced to the ordered form: 1 7 2 5
Figure 00000005
1 2 5 7. The ordered sequence 1 2 5 7 is sent to the block of negative decisions 5, where it is lexicographically compared with patterns of forbidden permutations leading to the formation of degenerate matrices, which clearly does not allow obtaining an equivalent code. The list of such permutations for the code (7, 4, 3) is given in Table 1.

Figure 00000006
Figure 00000006

Лексикографическое сравнение полученного результата перестановки 1 2 5 7 с соответствующей областью упорядоченного списка из таблицы 1 показывает, что совпадение отсутствует и возможность получения комбинации эквивалентного кода есть. Поэтому по результату поиска блок упорядоченных оценок 4направляетобе части сохраненных в его памяти нумераторов вектора Vпpc в виде двух последовательностей 1 7 2 5 3 6 4 в блок нумераторов 6, а ранжированная последовательность 1 2 5 7 из блока отрицательных решений направляется в блок когнитивной карты 7 для последующей ее обработки. Структура когнитивной карты декодера и организация ее памяти для быстрого поиска требуемой перестановки показаны в таблице 2.A lexicographic comparison of the obtained result of the permutation 1 2 5 7 with the corresponding region of the ordered list from Table 1 shows that there is no coincidence and the possibility of obtaining a combination of an equivalent code exists. Therefore, according to the search result, the block of ordered estimates 4 directs both parts of the enumerators of the vector V пpc stored in its memory in the form of two sequences 1 7 2 5 3 6 4 to the block of numerators 6, and the ranked sequence 1 2 5 7 from the block of negative decisions is sent to the block of the cognitive map 7 for its subsequent processing. The structure of the cognitive map of the decoder and the organization of its memory for a quick search for the required permutation are shown in Table 2.

Figure 00000007
Figure 00000007

Жирным шрифтом в ячейках таблицы выделены номера эталонных проверочных частей порождающих матриц эквивалентных кодов. Таких матриц в блоке 7 хранится всего четыре. Получив последовательность 1 2 5 7, блок когнитивной карты 7 отыскивает соответствующий номер проверочной матрицы, который направляется в блок перестановок эталонной матрицы 8. Образцы проверочных частей порождающих матриц эквивалентных кодов приведены ниже.The numbers of the reference verification parts of the generating matrices of equivalent codes are highlighted in bold in the table cells. There are only four such matrices in block 7. Having received the sequence 1 2 5 7, the block of the cognitive map 7 looks for the corresponding number of the check matrix, which is sent to the block of permutations of the reference matrix 8. Samples of the check parts of the generating matrices of equivalent codes are given below.

Figure 00000008
Figure 00000008

Получив из блока отрицательных решений 5 комбинацию нумераторов 1 2 5 7, блок когнитивной карты 7 определяет, что в качестве эталонной матрицы должна быть использована матрица с номером 2. Матрица 2 извлекается из памяти блока перестановок эталонной матрицы и ей приписываются номера строк 7 1 2 5, а столбцам приписываются номера 6 3 4, как предписывает соответствующая ячейка когнитивной карты из таблицы 2. Образ требуемой ячейки из когнитивной карты имеет видHaving received a combination of numerators 1 2 5 7 from the block of negative decisions 5, the block of cognitive map 7 determines that the matrix with number 2 should be used as the reference matrix. Matrix 2 is retrieved from the memory of the block of permutations of the reference matrix and row numbers are assigned to it 7 1 2 5 , and the columns are assigned numbers 6 3 4, as prescribed by the corresponding cell of the cognitive map from Table 2. The image of the required cell from the cognitive map has the form

Figure 00000009
Figure 00000009

Извлечение и последовательность преобразования шаблона в соответствии с данными из блока нумераторов 6.Extract and sequence the transformation of the template in accordance with the data from the block of numbers 6.

Figure 00000010
Figure 00000010

Figure 00000011
Figure 00000011

К моменту завершения операции перестановок эталонной матрицы в блоке 8 из блока упорядоченных оценок 4 в блок жестких решений 10 поступает комбинация переставленных информационных битов 1 1 0 0 0 0 0. Этот блок выделяет информационные разряды из полученной последовательности направляет их в блок информационных разрядов 11. Таким образом блок 11 получит данные из блока 10 в виде последовательности бит 110 0, которые направляются в блок сложения 9 для формирования проверочной части кодового вектора за счет сложения данных первой и второй строки матрицы H2. Следовательно, 101⊕011=110. Эти данные направляются в накопитель комбинации 12, где объединяются информационные и проверочные разряды и в результате этого формируется вектор переставленного кода видаBy the time the operation of the permutations of the reference matrix in block 8 is completed, a combination of rearranged information bits 1 1 0 0 0 0 0 arrives from the block of ordered estimates 4 to the block of hard decisions 10. This block extracts information bits from the obtained sequence and directs them to the block of information bits 11. Thus Thus, block 11 will receive data from block 10 in the form of a sequence of bits 110 0, which are sent to the addition block 9 to form the check part of the code vector by adding the data of the first and second rows of the matrix H 2 . Therefore, 101⊕011 = 110. This data is sent to the drive combination 12, where the information and check bits are combined, and as a result, a vector of the rearranged code of the form

Figure 00000012
Figure 00000012

Упорядочение нумераторов полученного вектора (эти действия не производятся в генераторе комбинаций двоичного эквивалентного кода и представляются только в качестве доказательства справедливости выполненных действий) позволяют получить безошибочный векторOrdering the enumerators of the resulting vector (these actions are not performed in the generator of combinations of a binary equivalent code and are presented only as proof of the validity of the actions performed) allow you to obtain an error-free vector

Figure 00000013
Figure 00000013

В случае возникновения ситуации, когда перестановка нумераторов принимает вид, совпадающий с отрицательным решением, это решение возвращается в блок упорядоченных оценок 4 и происходит замена символа, стоящего на крайней правой позиции среди информационных разрядов на наиболее надежный символ из числа проверочных разрядов и далее процесс, осуществляется по описанному алгоритму.If a situation arises when the permutation of the enumerators takes the form coinciding with a negative decision, this decision is returned to the block of ordered estimates 4 and the symbol at the far right position among the information bits is replaced with the most reliable symbol from the number of check bits, and then the process is carried out according to the described algorithm.

Таким образом, рациональная организация алгоритма работы устройства относительно известных аналогов устраняет необходимость в повторных действиях с перестановками при уточнении вырожденности матриц и за счет введения блока сложения исключает процедуру матричного умножения при поиске проверочных разрядов двоичного эквивалентного кода.Thus, the rational organization of the operation algorithm of the device with respect to known analogs eliminates the need for repeated operations with permutations when clarifying the degeneracy of matrices and, by introducing an addition block, eliminates the matrix multiplication procedure when searching for check digits of a binary equivalent code.

Claims (1)

Генератор комбинаций двоичного эквивалентного кода, содержащий блок приема, выход которого через последовательно включенные блок мягких решений и накопитель оценок подключен к одному входу блока упорядоченных оценок, первый выход которого через блок отрицательных решений и его первый выход подключен к другому входу блока упорядоченных оценок, отличающийся тем, что дополнительно введены блок нумераторов, блок когнитивной карты, блок перестановок эталонной матрицы, блок сложения, блок жестких решений, блок информационных разрядов и накопитель комбинации, при этом второй выход блока упорядоченных оценок через блок нумераторов подключен к первому входу блока перестановок эталонной матрицы, а второй вход этого блока через блок когнитивной карты подключен к другому выходу блока отрицательных решений, тогда как выход блока перестановок эталонной матрицы подключен к первому входу блока сложения, выход которого соединен с первым входом накопителя комбинации, при этом второй вход этого блока подключен к другому выходу блока информационных разрядов, первый выход которого подключен к второму входу блока сложения, а третий выход блока упорядоченных оценок через блок жестких решений подключен к входу блока информационных разрядов.A generator of combinations of a binary equivalent code containing a receiving block, the output of which is connected to one input of the block of ordered estimates through a series of soft decisions and an accumulator of estimates, the first output of which is through a block of negative decisions and its first output is connected to another input of the block of ordered estimates, which differs in that that additionally a block of enumerators, a block of a cognitive map, a block of permutations of a reference matrix, an addition block, a block of hard decisions, a block of information bits and a combination accumulator are introduced, while the second output of the block of ordered estimates through the block of enumerators is connected to the first input of the block of permutations of the reference matrix, and the second input of this block through the cognitive map block is connected to another output of the block of negative decisions, while the output of the permutation block of the reference matrix is connected to the first input of the addition block, the output of which is connected to the first input of the combination drive, while the second input of this block is under connected to another output of the block of information bits, the first output of which is connected to the second input of the addition block, and the third output of the block of ordered estimates through the block of hard decisions is connected to the input of the block of information bits.
RU2019140308A 2019-12-06 2019-12-06 Binary equivalent code combination generator RU2743854C1 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
RU2019140308A RU2743854C1 (en) 2019-12-06 2019-12-06 Binary equivalent code combination generator

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
RU2019140308A RU2743854C1 (en) 2019-12-06 2019-12-06 Binary equivalent code combination generator

Publications (1)

Publication Number Publication Date
RU2743854C1 true RU2743854C1 (en) 2021-03-01

Family

ID=74857423

Family Applications (1)

Application Number Title Priority Date Filing Date
RU2019140308A RU2743854C1 (en) 2019-12-06 2019-12-06 Binary equivalent code combination generator

Country Status (1)

Country Link
RU (1) RU2743854C1 (en)

Citations (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050071728A1 (en) * 2001-08-27 2005-03-31 Yan-Xiu Zheng Encoding and decoding apparatus and method
US20050210358A1 (en) * 2002-05-31 2005-09-22 Koninklijke Phillips Electronics N.V. Soft decoding of linear block codes
RU2438252C1 (en) * 2010-05-07 2011-12-27 Федеральный научно-производственный центр Открытое акционерное общество "Научно-производственное объединение "Марс" High correcting capacity decoder
RU2490804C1 (en) * 2012-07-03 2013-08-20 Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Ульяновский государственный технический университет" Ordered symbol statistics decoder
RU2538331C2 (en) * 2013-05-20 2015-01-10 Федеральный научно-производственный центр Открытое акционерное общество "Научно-производственное объединение "Марс" Serial turbo code soft decoder
RU2580797C1 (en) * 2015-03-13 2016-04-10 Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Ульяновский государственный технический университет" Method of soft decoding of block codes
RU2644507C1 (en) * 2017-01-09 2018-02-12 Федеральный научно-производственный центр акционерное общество "Научно-производственное объединение "Марс" Resetting decoder with training mode
RU2646372C1 (en) * 2016-10-31 2018-03-02 Государственное бюджетное образовательное учреждение высшего образования Нижегородский государственный инженерно-экономический университет (НГИЭУ) Method of soft cognitive decoding of systematic block codes
RU2697732C1 (en) * 2018-07-11 2019-08-19 федеральное государственное бюджетное образовательное учреждение высшего образования "Ульяновский государственный технический университет" Method for permutational decoding of block codes based on ordered cognitive map
RU2699833C1 (en) * 2018-11-08 2019-09-11 Валерий Владимирович Золотарев Method of accelerated decoding of a linear code

Patent Citations (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050071728A1 (en) * 2001-08-27 2005-03-31 Yan-Xiu Zheng Encoding and decoding apparatus and method
US20050210358A1 (en) * 2002-05-31 2005-09-22 Koninklijke Phillips Electronics N.V. Soft decoding of linear block codes
RU2438252C1 (en) * 2010-05-07 2011-12-27 Федеральный научно-производственный центр Открытое акционерное общество "Научно-производственное объединение "Марс" High correcting capacity decoder
RU2490804C1 (en) * 2012-07-03 2013-08-20 Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Ульяновский государственный технический университет" Ordered symbol statistics decoder
RU2538331C2 (en) * 2013-05-20 2015-01-10 Федеральный научно-производственный центр Открытое акционерное общество "Научно-производственное объединение "Марс" Serial turbo code soft decoder
RU2580797C1 (en) * 2015-03-13 2016-04-10 Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Ульяновский государственный технический университет" Method of soft decoding of block codes
RU2646372C1 (en) * 2016-10-31 2018-03-02 Государственное бюджетное образовательное учреждение высшего образования Нижегородский государственный инженерно-экономический университет (НГИЭУ) Method of soft cognitive decoding of systematic block codes
RU2644507C1 (en) * 2017-01-09 2018-02-12 Федеральный научно-производственный центр акционерное общество "Научно-производственное объединение "Марс" Resetting decoder with training mode
RU2697732C1 (en) * 2018-07-11 2019-08-19 федеральное государственное бюджетное образовательное учреждение высшего образования "Ульяновский государственный технический университет" Method for permutational decoding of block codes based on ordered cognitive map
RU2699833C1 (en) * 2018-11-08 2019-09-11 Валерий Владимирович Золотарев Method of accelerated decoding of a linear code

Similar Documents

Publication Publication Date Title
Srinivasavaradhan et al. Trellis BMA: Coded trace reconstruction on IDS channels for DNA storage
CN102694625B (en) Polarization code decoding method for cyclic redundancy check assistance
US11700545B2 (en) Method and device for transmitting data
CN110278002B (en) Polar Code Belief Propagation List Decoding Method Based on Bit Flip
CN101867379B (en) A Decoding Method of Convolutional Codes Aided by Cyclic Redundancy Check
Shpilka Capacity-achieving multiwrite WOM codes
Barg et al. On the complexity of minimum distance decoding of long linear codes
Abu-Sini et al. On Levenshtein’s reconstruction problem under insertions, deletions, and substitutions
CN108574494B (en) Coding and decoding method and device
CN109257140B (en) Polarized channel reliability sequencing method, polarized code encoding method and polarized code encoding device
Gabrys et al. Codes correcting erasures and deletions for rank modulation
Chee et al. Codes correcting limited-shift errors in racetrack memories
JPWO2019130475A1 (en) Error correction coding method and device using channel polarization, decoding method and device
Sini et al. Reconstruction of sequences in DNA storage
Schoeny et al. Novel combinatorial coding results for DNA sequencing and data storage
US11038738B2 (en) Encoding method and encoder for (n,n(n-1),n-1) permutation group code in communication modulation system
CN111130567B (en) Belief Propagation List Decoding Method for Polar Codes with Added Noise Perturbation and Bit Flip
RU2743854C1 (en) Binary equivalent code combination generator
CN110995279A (en) Polarization code combined SCF spherical list overturning decoding method
Levick et al. Achieving the capacity of a DNA storage channel with linear coding schemes
CN101552613B (en) Low density check code decoding method based on outer information symbol variation
RU2644507C1 (en) Resetting decoder with training mode
Gelles et al. Potent tree codes and their applications: Coding for interactive communication, revisited
CN111130565B (en) Decoding method and device based on neural network
Banerjee et al. Correcting a single deletion in reads from a nanopore sequencer