Способ перемежения кодовых символов в коде с низкой плотностью проверок на четность Российский патент 2021 года по МПК H03M13/11 

Изобретение относится к области теории кодирования, в частности к системам кодирования с исправлением ошибок с целью повышения эффективности использования спектра при передаче данных в цифровой системе радиосвязи.

В классе линейных блоковых кодов можно особо выделить подкласс кодов с низкой плотностью проверок на четность [Gallager R. “Low Density Parity Check Codes”// MIT Press 1963. Особенностью данного кода является наличие простой графической модели алгоритма декодирования определяемого как декодирование на графе (фиг. 1). Декодирование на графе следует понимать в том смысле, что граф определяет разбиение всего кодового слова на более короткие коды, причем короткие коды могут перекрываться друг с другом. Избежать данных перекрытий можно путем повторения перекрывающихся кодовых символов. Разные копии принятого кодового символа или мягкого решения об этом символе входят в различные кодовые слова более короткого кода, при этом все кодовые слова короткого кода могут быть декодированы независимо. Такая структура может быть представлена в виде двудольного графа один тип вершин, которого ассоциирован с кодовыми символами, причем количество ребер исходящих из каждой вершины соответствует количеству повторений кодового символа (переменная вершина обозначена прямоугольником). Другой тип вершин соответствует коротким кодам, причем каждая вершина есть кодовое слово с количеством кодовых символов равным числу входящих ребер (проверочная вершина обозначена кругом). Каждой проверочной вершине может быть приписана контрольная сумма, как индикатор наличия ошибок в коротком коде. Переменные вершины могут быть соединены только с проверочными вершинами, и, наоборот, проверочные вершины могут быть соединены только с переменными вершинами, что позволяет рассматривать граф как двудольный.

Такой двудольный граф называют графом Таннера [Tanner R.M. A Recursive Approach to Low Complexity Codes / R.M. Tanner // IEEE Transaction on Information Theory. - 1981. -Vol. IT27, № 9. - P. 533547]. По сути для линейного блокового кода граф Таннера является графическим представлением проверочной матрицы. Безошибочное декодирование характеризуется равенством нулю всех контрольных сумм - кодовых ограничений.

Код с низкой плотностью проверок на четность может быть декодирован в мягких решениях, используя алгоритм обмена сообщений (фиг. 1). Алгоритм обмена сообщениями [Gallager R. “Low Density Parity Check Codes”// MIT Press 1963] инициализируют каждый переменную вершину информацией о достоверности приема каждого символа (мягким решением), полученной из канала.

Вычисляют значение исходящего сообщения от переменной вершины равного апостериорной вероятности для кодового символа принять определенное значение кодового символа, отнесенного к этому переменной вершине для каждого ребра двудольного графа.

В каждой проверочной вершине модифицируют исходящие сообщения от тех переменных вершин, с которым они связаны ребром двудольного графа, и для которого они являются входящими, ставя в соответствие каждому ребру исходящие сообщения проверочной вершине, которые равны второму набору вероятностей для кодового символа принять определенное значение.

Обновляют исходящие сообщение переменной вершине входящими сообщениями, которые являются исходящими сообщениями проверочной вершине.

Повторяют итерации определенное число раз или до тех пор, пока кодовые ограничения не будут выполнены.

Знак исходящего сообщения выбирают таким, чтобы удовлетворить кодовым ограничениям. Абсолютное значение исходящего сообщения вычисляют при помощи функции . Эта функция является решающей функцией или логарифмом отношения правдоподобия. Функция обладает коммутативностью:

Есть несколько методов для определения функции . Наиболее простой известен как алгоритм “min-sum”. Абсолютное значение исходящего сообщения равно минимальному абсолютному значению среди входящих сообщений за исключением сообщения от той вершины, для которого предназначено данное исходящее сообщение:

Другой метод задания функции состоит в определении функции через функцию , применяемую в LOG MAP алгоритме [Pietrobon S.S. Implementation and Performance of a Turbo/MAP Decoder / S.S. Pietrobon // International J. of Satellite Communication. - 1998. Vol. 16 (Jan-Feb). - P. 23-46]. Функция может быть задана как:

Где функция , может быть представлена в виде таблицы.

Существует модификация предложенного метода, где дополнительное слагаемое определено как:

Модификации этого алгоритма приведена в [W.K Leung,W.L Lee,A.Wu,L.Ping,“ Efficient implementation technique of LDPC decoder ”Electron.Lett..,vol.37(20),pp.1231-1232,Sept2001]. Данный метод не требует таблицы, но приводит к некоторому ухудшению характеристик, но зато позволяет сократить число операций при декодировании.

Следуя терминологии из [П. Камерон, Дж. Ван Линт “Теория графов теория кодирования и блок-схемы”// M. Наука 1980], определим путь на графе как последовательность вершин, в которой соседние вершины смежные. Цикл - это путь, где начальные и конечные точки совпадают. Граф связен, если между любыми двумя вершинами существует путь, а метрикой расстояния между двумя вершинами будем считать длину кратчайшего пути между ними. Диаметром графа будем считать наибольшее значение расстояния между двумя любыми вершинами в графе, а обхватом графа - длину кратчайшего цикла без повторяющихся ребер при условии, что такой цикл существует. Валентностью вершины будем называть количество ребер, исходящих из этой вершины или количество вершин смежных данной. Если все вершины графа имеют одинаковую валентность, то граф будем называть регулярным. Эффективность декодирования на графе в первую очередь зависит от структуры графа, а именно от наличия на графе дефектов в виде структур, приводящим к кодовым словам с низким весом. Одним из таких дефектов является “останавливающее множество” [Tom Richardson y Rudiger Urbanke “The Capacity of Low-Density Parity-Check Codes under Message-Passing Decoding”// March 9, 2001], а так же петель или циклов [David MacKay, Good Error-Correcting Codes Based on Very Sparse Matrices// IEEE Transaction on information theory, Vol 45, march 1999], где “останавливающее множество” как подмножество проверочных вершин, для которого не существует переменных вершин, соединенных единственным ребром с каким-либо из проверочных вершин, входящих в это подмножество. Множество переменных вершин, соединенных с останавливающим подмножеством, содержит наиболее вероятные комбинации ошибок. Однако, как было отмечено выше, граф может быть задан путем отдельного задания шаблона повторения и группирования, а также закона перемежения. Причем, предполагая идеальное перемежение, получены оптимизированные шаблоны повторения-группирования, которые основаны на неравномерном повторении [H. Jin, A. Khandekar and R. J. McEliece, “Irregular repeat-accumulate codes," Proceedings of the Second International Symposium on Turbo Codes and Related Topics, pp. 18, Brest, France, September 2000], [Thomas J. Richardson and Rüdiger L Urbanke . Efficient Encoding of Low-Density Parity Check Codes]. В связи с этим актуальной является задача отдельной разработки перемежителя, позволяющего построить по известным оптимизированным шаблонам повторения-группирования двудольный граф, содержащий наименьшее число дефектов.

В настоящее время широкую известность получил класс “турбо-образных” (“turbo-like”) кодов, среди которых выделяются коды с “повторением - накоплением”, известные из [H. Jin, A. Khandekar and R. J. McEliece, “Irregular repeat-accumulate codes," Proceedings of the Second International Symposium on Turbo Codes and Related Topics, pp. 1-8, Brest, France, September 2000]. Кодирование кодов с “повторением - накоплением” осуществляют в следующем порядке: повторение каждого информационного символа, перемежение повторенных символов, накопление суммы по модулю 2 перемеженных символов. Данные коды обладают свойствами, как турбо-кодов, так и кодов с низкой плотностью проверок на четность и могут быть декодированы как в параллельном режиме - алгоритм обмена сообщениями, так и в последовательном режиме - алгоритм MAP. Следует отметить, что в последнем случае алгоритм по существу является гибридным, состоящим из MAP алгоритма декодирования сверточного кода с двумя состояниями и алгоритма обмена сообщениями с неравномерно повторенными информационными символами [J. Li, Low-Complexity, Capacity-Approaching Coding Schemes: Design, Analysis and Applications, Ph.D. dissertation, Texas A&M University, 2002. ]. Из [H. Jin, A. Khandekar and R. J. McEliece, “Irregular repeat-accumulate codes," Proceedings of the Second International Symposium on Turbo Codes and Related Topics, pp. 1-8, Brest, France, September 2000] известно, что наибольшая эффективность от применения достигается неравномерным или иррегулярным повторением информационных символов. Кроме того, характеристики кодов повторения с накоплением в большой степени характеризуются перемежителем, который совместно с шаблоном иррегулярного повторения и шаблоном накопления контрольных сумм определяют граф Таннера для данного кода. Требования к перемежителю заключаются в том, чтобы обеспечить достаточное разнесение повторенных символов, обеспечив тем самым отсутствие или малое число кодовых слов с низким весом. Существуют два класса перемежителей: случайный и детерминистический. Для формирования случайного перемежителя применяют датчик случайных чисел, при помощи которого определяют номер перемежаемого символа в последовательности после перемежения. Последовательность получаемых номеров подвергают проверке на достаточность разнесения подряд идущих повторенных информационных символов с выбраковкой (откатом назад) последовательностей, не прошедших подобной проверки. Известен, в частности, алгоритм S-random [S. Dolinar and D. Divsalar “Weight Distribution for turbo codes using random and non-random permutation” JPL Progress report 42-122 pp 56-65 Aug 15,1995]. Известен патент [United States Patent 6,453,442 Sadjadpour, et al., September 17, 2002 Two stage S--Random interleaver], где реализован модифицированный S-random алгоритм.

Псевдослучайные перемежители требуют много памяти для хранения и не могут быть сгенерированы на приемной и передающей стороне независимо или же такая генерация потребует больших вычислительных и временных затрат. От этого недостатка свободны детерминистические перемежители, где способ взаимно однозначного соответствия перемежения определяется путем задания параметризованного алгоритма. Такие перемежителя могут формироваться “на лету”, то есть непосредственно в процессе декодирования, и задаются путем определения параметров алгоритма (несколько положительных целых чисел).

Известно решение, представляющее собой псевдослучайный взаимно простой интерливер, [United States Patent 6,857,087 Crozier, et al. February 15, 2005 High-performance low-memory interleaver banks for turbo-codes]. Такой способ, известный как DRP перемежитель, заключается в перемежении последовательности упорядоченных элементов, сформированных как подпоследовательностей, где каждая подпоследовательность содержит в среднем элементов. При этом

перемежают элементы в каждой из подпоследовательностей для формирования последовательности из упорядоченных элементов по правилу, установленному в пилотной подпоследовательности, формируя пилотную псевдослучайную подпоследовательность;

перемежают элементов в пилотной псевдослучайной последовательности из упорядоченных элементов для формирования перемеженной последовательности, сформированной как подпоследовательностей, имеющих размер в среднем элементов;

перемежают элементы внутри каждой из подпоследовательности для получения перемеженной последовательности из упорядоченных элементов.

Существенной особенностью данного способа является то, что шаг 2 выполняют путем взаимно-простого перемежителя, соответствующего преобразованию вида , где - количество перемежаемых элементов, а - старый номер в первой перемеженной последовательности - число взаимно простое с . Подобный подход также известен из [S. Dolinar and D. Divsalar “Weight Distribution for turbo codes using random and non-random permutation” JPL Progress report 42-122 pp 56-65 Aug 15,1995] как алгебраический интерливер. Подбор чисел целесообразно таким образом, чтобы обеспечить наименьшее число кодовых слов с минимальным весом, что так же отвечает критерию минимума циклов длиной 4 на графе Таннера. Однако данный способ не гарантирует эффективности при коротком ( бит) размере блока.

Из [J. Sun and O.Y. Takeshita. Interleavers for turbo codes using permutation polynomials over integer rings. IEEE Trans.Inform. Theory, vol.51, Jan. 2005] известен ARP интерливер. Интерливер ARP (почти регулярный перемежитель) представляет собой преобразование вида: . Это преобразование есть модификация классического интерливера (запись по строкам - чтение по столбцам) с внесенной флуктуацией, определяемой функцией .

Из патента US 8239711 "QPP interleaver/de-interleaver for turbo codes" известен следующий способ перемежения кодовых символов.

Входные биты внутреннего перемежителя турбокода обозначены как , где N - количество входных бит. Выходные биты внутреннего интерливера турбокода обозначены как .

Входные и выходные номера связаны следующим соотношением:

,

Где выходной индекс и входной индекс связаны следующей квадратичной формой:

Параметры и зависят от размера блока . QPP перемежение может быть выполнено рекурсивно: где , а .

Для того чтобы эта схема была реализуемой, работа перемежителей не должна приводить к конфликтам при доступе к памяти. К числу таких конфликтов можно, например, отнести попытку одновременной записи и чтения отдельной ячейки памяти. Память обычно реализуют в виде блоков (“банков”) памяти, таким образом, что к каждому блоку за один квант времени возможен либо доступ на запись (по указанному адресу), либо доступ на чтение. Условие может быть записано в следующем виде:

Где , , . Особо выделим перемежители, для которых это свойство выполняется при любом . Назовем такой перемежитель максимально свободным от конфликтов памяти.

Пусть и , тогда

Нам надо доказать, что если . Далее рассмотрим два случая: перемежитель QPP и перемежитель ARP.

1) QPP:

Таким образом, мы видим, что последнее выражение не зависит от , и если мы предположим, что , то следствием этого будет , что противоречит свойству перемежителя: функция определяет взаимно однозначное отображение на заданном интервале.

2) ARP:

Последнее выражение не зависит от только в том случае, если по определению функции .

Далее доказательство аналогично при условии, что .

В основе заявляемого способа классический иррегулярный код повторений с накоплениями с низкой плотностью проверок на четность [D. Divsalar, H. Jin, and R. J. McEliece. "Coding theorems for ‘turbo-like’ codes." Proc. 36th Allerton Conf. on Communication, Control and Computing, Allerton, Illinois, Sept. 1998, pp. 201-210.], где применен новый эффективный перемежитель.

Наиболее близким аналогом по технической сущности к предлагаемому является способ перемежения кодовых символов, представленный в патенте РФ 2700398 "Способ передачи данных в системе цифровой радиосвязи на основе кодов с низкой плотностью проверок на четность и способ перемежения кодовых символов", H03M 13/11, 13/27, 13/29, принятый за прототип.

Способ-прототип перемежения последовательности кодовых символов, состоит в том, что:

разбивают последовательность символов для перемежения на подпоследовательности символов для перемежения;

осуществляют обмен кодовыми символами между и/или внутри подпоследовательностей, образуя перемеженные подпоследовательности кодовых символов;

формируют из подпоследовательностей финальную перемеженную последовательность;

последовательность символов для перемежения количеством разбивают на равные подпоследовательности установленного размера ;

в каждой из подпоследовательностей производят перемежение по установленному правилу перемежения подпоследовательностей, для этого

формируют пилотную псевдослучайную подпоследовательность таким образом, что в пилотной подпоследовательности выполняется условие , где - номера кодовых символов до перемежения а - номера тех же кодовых символов после перемежения, - целое положительное число;

для определения пилотной псевдослучайной подпоследовательности номеров формируют множество номеров от до , где - количество символов для перемежения следующим образом:

устанавливают начальное целые положительные значение параметра разнесения ;

формируют множество пар чисел определяющих закон взаимно однозначного соответствия между первоначальной последовательностью символов и перемеженной подпоследовательностью символов, состоящее из одной пары чисел, где первое число - номер в подпоследовательности до перемежения, а второе число - номер элемента в подпоследовательности после перемежения, где в вышеупомянутой паре чисел первое равно нулю и второе равно случайным образом выбранному номеру из множества , который при этом исключают из множества ;

инициализируют ;

случайным образом выбирают из множества элемент и ставят ему взаимно однозначное соответствие элемента , определяя таким образом преобразование ;

выполняют проверку дистанционного разнесения перемеженных символов для чего для всех таких, что , вычисляют значение ;

если все полученные значения разные, то увеличивают значение , исключают элемент из множества и добавляют в множество пару ;

если хотя бы две разности оказываются равны, то повторно выбирают другой элемент из множества и повторяют для него проверку дистанционного разнесения перемеженных символов;

при невозможности найти элемент, удовлетворяющий проверке дистанционного разнесения перемеженных символов, повторяют весь алгоритм заново с уменьшенным параметром разнесения ;

повторяют процедуру до тех пор, пока множество не станет пустым, а множество не будет содержать пар чисел;

формируют перемеженные подпоследовательности, располагая элементы в соответствии с их новыми номерами в каждой подпоследовательности, используя пилотную псевдослучайную последовательность номеров;

объединяют перемеженные подпоследовательности в первую перемеженную последовательность;

в первой перемеженной последовательности выполняют второе перемежение для чего для каждого символа в последовательности формируют его новый номер в последовательности по порядку путем выполнения преобразования вида , где - количество перемежаемых элементов, а - старый номер в первой перемеженной последовательности, - число взаимно простое с ;

формируют вторую перемеженную последовательность, располагая элементы первой перемеженной последовательности в соответствии с новыми номерами;

для каждого -того элемента, начиная с первого, получают новый номер во второй перемеженной последовательности, где новый номер равен , при этом номера остальных элементов последовательности не изменяют;

формируют финальную перемеженную последовательность, располагая элементы в соответствии с их новыми номерами.

В способе-прототипе шаг получения второй перемеженной последовательности путем линейного алгебраического перемежения: не является оптимальным, выбор линейной функции не охватывает всех вариантов перемежения, следовательно, алгоритм может быть улучшен путем выбора целевой функции и выполнения дополнительных шагов по ее оптимизации. В связи с этим актуальной является разработка перемежителя, который бы обеспечивал максимально достижимые характеристики помехоустойчивого кодирования и сохранял возможность параллельной реализации алгоритма перемежения как в прототипе.

Задача, которую решает заявляемый способ, состоит в снижении вероятности ошибки при помехоустойчивом кодировании за счет улучшения дистанционных свойств перемежителя.

Для решения поставленной задачи в способе, перемежения последовательности кодовых символов, состоящем в том, что разбивают последовательность символов для перемежения на подпоследовательности символов для перемежения, осуществляют обмен кодовыми символами между и/или внутри подпоследовательностей, образуя перемеженные подпоследовательности кодовых символов, формируют из подпоследовательностей финальную перемеженную последовательность, последовательность символов для перемежения количеством разбивают на равные подпоследовательности установленного размера , в каждой из подпоследовательностей производят перемежение по установленному правилу перемежения подпоследовательностей, для этого формируют пилотную псевдослучайную подпоследовательность таким образом, что в пилотной подпоследовательности выполняется условие

, где - номера кодовых символов до перемежения, а - номера тех же кодовых символов после перемежения, - целое положительное число, для определения пилотной псевдослучайной подпоследовательности номеров формируют множество номеров от до , где - количество символов для перемежения следующим образом: устанавливают начальные целые положительные значение параметра разнесения , формируют множество пар чисел , определяющих закон взаимно однозначного соответствия между первоначальной последовательностью символов и перемеженной подпоследовательностью символов, состоящее из одной пары чисел, где первое число - номер в подпоследовательности до перемежения, а второе число - номер элемента в подпоследовательности после перемежения, где в вышеупомянутой паре чисел первое равно нулю и второе равно случайным образом выбранному номеру из множества , который при этом исключают из множества , инициализируют , случайным образом выбирают из множества элемент и ставят ему во взаимно однозначное соответствие элемент , определяя таким образом преобразование , выполняют проверку дистанционного разнесения перемеженных символов, для чего для всех таких, что , , вычисляют значение , если все полученные значения разные, то увеличивают значение , исключают элемент из множества и добавляют во множество пару , если хотя бы две разности оказываются равны, то повторно выбирают другой элемент из множества и повторяют для него проверку дистанционного разнесения перемеженных символов, при невозможности найти элемент, удовлетворяющий проверке дистанционного разнесения перемеженных символов, повторяют весь алгоритм заново с уменьшенным параметром разнесения , повторяют процедуру до тех пор, пока множество не станет пустым, а множество не будет содержать пар чисел, формируют перемеженные подпоследовательности, располагая элементы в соответствии с их новыми номерами в каждой подпоследовательности, используя пилотную псевдослучайную последовательность номеров, объединяют перемеженные подпоследовательности в первую перемеженную последовательность, в первой перемеженной последовательности выполняют второе перемежение для чего для каждого символа в последовательности формируют его новый номер в последовательности по порядку путем выполнения преобразования вида , где - количество перемежаемых элементов, а - старый номер в первой перемеженной последовательности, - число взаимно простое с , формируют вторую перемеженную последовательность, располагая элементы первой перемеженной последовательности в соответствии с новыми номерами, для каждого -того элемента, начиная с первого, получают новый номер во второй перемеженной последовательности, где новый номер равен , при этом номера остальных элементов последовательности не изменяют, формируют третью перемеженную последовательность, располагая элементы в соответствии с их новыми номерами согласно изобретению, для первых K элементов в третьей перемеженной последовательности вычисляют функцию дистанционного разнесения перемежителя для каждого из первых K элементов для чего для произвольного номера находят ; обратным преобразованием получают ; обратным преобразованием получают ; находят обратным преобразованием получают ; обратным преобразованием получают ; находят ; обратным преобразованием получают ; обратным преобразованием получают ; сортируют вектор, составленный из индексов по возрастанию, получая сортированный вектор ; делают циклическую перестановку в векторе вида получают вектор ; вычитают из вектора вектор находят в результирующем векторе минимум по абсолютной величине, который и является значением функции дистанционного разнесения перемежителя для элемента с номером , определяют элементов с наименьшим значением этой функции, индексы которых осуществляют все возможные циклические перестановки элементов третьей последовательности для которых выполняется таким образом, что , где , для каждой перестановки вычисляют функцию дистанционного разнесения для каждого из первых K элементов перемеженной третьей последовательности, выбирают в качестве четвертой перемеженной последовательности ту, где минимальное значение функции дистанционного разнесения максимально, определяют элементов с наименьшим значением этой функции и итеративно повторяют процесс оптимизации путем выполнения циклических перестановок и определения той перестановки, где минимальное значение функции дистанционного разнесения максимально до тех пор, пока не достигнут заранее заданного порога минимального значения функции дистанционного разнесения, формируя тем самым как последовательность циклических сдвигов длиной , каждый из элементов которой , где - номер итерации, так и финальную последовательность перемеженных символов.

Графические материалы, используемые в описании:

Фиг. 1 - алгоритм декодирования на графе - обмен сообщениями.

Фиг. 2 - граф Петерсона и заданный на нем код по способу Таннера.

Фиг. 3 - способ перемежения кодовых символов.

Фиг. 4 - блок-схема устройства для осуществления предлагаемого способа.

Фиг. 5 - результаты моделирования.

Заявляемый способ перемежения кодовых символов в цифровой системе связи на основе кодов с низкой плотностью проверок на четность, заключается в том, что

разбивают последовательность символов для перемежения на подпоследовательности символов для перемежения;

осуществляют обмен кодовыми символами между и/или внутри подпоследовательностей, образуя перемеженные подпоследовательности кодовых символов;

формируют из подпоследовательностей финальную перемеженную последовательность;

последовательность символов для перемежения количеством разбивают на равные подпоследовательности установленного размера ;

в каждой из подпоследовательностей производят перемежение по установленному правилу перемежения подпоследовательностей, для этого формируют пилотную псевдослучайную подпоследовательность таким образом, что в пилотной подпоследовательности выполняется условие , где - номера кодовых символов до перемежения, а - номера тех же кодовых символов после перемежения, - целое положительное число;

для определения пилотной псевдослучайной подпоследовательности номеров формируют множество номеров от до , где - количество символов для перемежения следующим образом:

устанавливают начальное целые положительные значение параметра разнесения ;

формируют множество пар чисел , определяющих закон взаимно однозначного соответствия между первоначальной последовательностью символов и перемеженной подпоследовательностью символов, состоящее из одной пары чисел, где первое число - номер в подпоследовательности до перемежения, а второе число - номер элемента в подпоследовательности после перемежения, где в вышеупомянутой паре чисел первое равно нулю и второе равно случайным образом выбранному номеру из множества , который при этом исключают из множества ;

инициализируют ;

случайным образом выбирают из множества элемент и ставят ему взаимно однозначное соответствие элемент , определяя таким образом преобразование ;

выполняют проверку дистанционного разнесения перемеженных символов для чего

для всех таких, что , , вычисляют значение ;

если все полученные значения разные, то увеличивают значение , исключают элемент из множества и добавляют в множество пару ;

если хотя бы две разности оказываются равны, то повторно выбирают другой элемент из множества и повторяют для него проверку дистанционного разнесения перемеженных символов;

при невозможности найти элемент, удовлетворяющий проверке дистанционного разнесения перемеженных символов, повторяют весь алгоритм заново с уменьшенным параметром разнесения ;

повторяют процедуру до тех пор, пока множество не станет пустым, а множество не будет содержать пар чисел;

формируют перемеженные подпоследовательности, располагая элементы в соответствии с их новыми номерами в каждой подпоследовательности, используя пилотную псевдослучайную последовательность номеров;

объединяют перемеженные подпоследовательности в первую перемеженную последовательность;

в первой перемеженной последовательности выполняют второе перемежение для чего

для каждого символа в последовательности формируют его новый номер в последовательности по порядку путем выполнения преобразования вида , где - количество перемежаемых элементов, а - старый номер в первой перемеженной последовательности, - число взаимно простое с ;

формируют вторую перемеженную последовательность, располагая элементы первой перемеженной последовательности в соответствии с новыми номерами;

для каждого -того элемента, начиная с первого, получают новый номер второй перемеженной последовательности, где новый номер равен , при этом номера остальных элементов последовательности не изменяют;

формируют третью перемеженную последовательность, располагая элементы в соответствии с их новыми номерами;

для первых K элементов в третьей перемеженной последовательности вычисляют функцию дистанционного разнесения перемежителя для каждого из первых K элементов для чего

для произвольного номера находят ;

обратным преобразованием получают ;

обратным преобразованием получают ;

находят ;

обратным преобразованием получают ;

обратным преобразованием получают ;

находят ;

обратным преобразованием получают ;

обратным преобразованием получают ;

сортируют вектор, составленный из индексов по возрастанию, получая сортированный вектор ;

делают циклическую перестановку в векторе вида получают вектор ;

вычитают из вектора вектор , находят в результирующем векторе минимум по абсолютной величине, который и является значением функции дистанционного разнесения перемежителя для элемента с номером ;

определяют элементов с наименьшим значением этой функции, индексы которых ;

осуществляют все возможные циклические перестановки элементов третьей последовательности, для которых выполняется таким образом, что , где , для каждой перестановки вычисляют функцию дистанционного разнесения для каждого из первых K элементов перемеженной третьей последовательности, выбирают в качестве четвертой перемеженной последовательности, ту, где минимальное значение функции дистанционного разнесения максимально;

определяют элементов с наименьшим значением этой функции и итеративно повторяют процесс оптимизации путем выполнения циклических перестановок и определения той перестановки, где минимальное значение функции дистанционного разнесения максимально до тех пор, пока не достигнут заранее заданного порога минимального значения функции дистанционного разнесения, формируя тем самым как последовательность циклических сдвигов длиной , каждый из элементов которой , где - номер итерации, так и финальную последовательность перемеженных символов.

Для пояснения на фиг. 3 представлен алгоритм предлагаемого способа перемежения кодовых символов.

Отличие от прототипа заключается во введении последовательности циклических сдвигов , которая максимизирует метрику - упрощенную функцию дистанционного разнесения в результате итеративного поиска максимума этой функции путем циклического сдвига индексов в банках памяти. Каждый дополнительный циклический сдвиг выполняют в соответствующем банке памяти, что позволяет за один такт считывать или записывать параллельно мягких решений в банков памяти.

Предлагаемый способ может быть реализован устройством, блок-схема которого изображена на фиг. 4, где обозначено:

1 - блок управления (БУ);

2.1 - 2.K - генератор адресов (ГА);

3.1 -3.K - блок памяти (БА).

Устройство (перемежитель) содержит блок управления 1, первый выход которого соединен с входами K генераторов адресов 2.1 - 2K, выходы которых соединены с первыми входами соответствующих блоков памяти 3.1 - 3.K, вторые входы которых подсоединены ко второму выходу блока управления. Третьи входы блоков памяти 3.1 - 3.K предназначены для входных данных, а выходы - выходных данных.

Функционирование устройства происходит следующим образом.

Сигналы с первого выхода блока управления 1 поступают на входы генераторов адресов 2.1 - 2.K, в котором они независимо формируют адреса для записи и чтения в блоках памяти 3.1 - 3.K и по сигналу синхронизации, поступающего на вторые входа блоков памяти 3.1 - 3.K со второго выхода блока управления 1 в блоках памяти 3.1 - 3.K осуществляют запись или чтение данных.

Задать правило перемежения удобно в виде прямоугольной матрицы, состоящей из столбцов и строк, где финальная перемеженная последовательность записана по строкам. Индексы финальной перемеженной последовательности соответствуют номерам повторенных кодовых символов.

Кодовый символ записывают в соответствующую его номеру строку и столбец. Каждые символов записывают в разных столбцов, с номерами строк, которые генерируют генераторы адресов 2.1 - 2.K на запись. Данные считывают из перемежителя по строкам с учетом дополнительных последовательности циклических сдвигов , формируя финальную перемеженную последовательность.

Для получения финальной перемеженной последовательности используют способ перемежения последовательности кодовых символов, описанный выше.

Сопоставительный анализ заявляемых способов с прототипом показывает, что предлагаемое изобретение существенно отличается от известных решений, так как позволяют повысить качество радиосвязи за счет выполнения дополнительных циклических сдвигов в каждом из банков перемежителя, повышая тем самым дистанционное разнесение кодовых символов в перемежителе, что снижает вероятность ошибки в радиоканале передачи данных.

Таким образом, заявляемый способ позволяет достичь энергетический выигрыш кодирования в среднем 0.5 Дб по сравнению с прототипом (фиг. 5). А также заявляемый способ, как и прототип, допускает параллельную реализацию декодирующего устройства без потери характеристик помехоустойчивости.

Изобретение относится к области теории кодирования, в частности к системам для объединенного кодирования с исправлением и обнаружением ошибок с целью повышения эффективности использования спектра при передаче данных в цифровой системе радиосвязи. Технический результат - способ позволяет существенно улучшить свойства дистанционного разнесения перемеженных символов, тем самым способствуя решению задачи повышения качества связи. Результат достигается за счет выполнения дополнительных циклических сдвигов в каждом из банков перемежителей, повышая тем самым дистанционное разнесение кодовых символов в перемежителе, что снижает вероятность ошибки в радиоканале передачи данных. 5 ил.

Способ перемежения последовательности кодовых символов, состоящий в том, что разбивают последовательность символов для перемежения на подпоследовательности символов для перемежения, осуществляют обмен кодовыми символами между и/или внутри подпоследовательностей, образуя перемеженные подпоследовательности кодовых символов, формируют из подпоследовательностей финальную перемеженную последовательность, последовательность символов для перемежения количеством разбивают на равные подпоследовательности установленного размера , в каждой из подпоследовательностей производят перемежение по установленному правилу перемежения подпоследовательностей, для этого формируют пилотную псевдослучайную подпоследовательность таким образом, что в пилотной подпоследовательности выполняется условие

, где - номера кодовых символов до перемежения, а - номера тех же кодовых символов после перемежения, - целое положительное число, для определения пилотной псевдослучайной подпоследовательности номеров формируют множество номеров от до , где - количество символов для перемежения следующим образом: устанавливают начальные целые положительные значения параметра разнесения , формируют множество пар чисел , определяющих закон взаимно однозначного соответствия между первоначальной последовательностью символов и перемеженной подпоследовательностью символов, состоящее из одной пары чисел, где первое число - номер в подпоследовательности до перемежения, а второе число - номер элемента в подпоследовательности после перемежения, где в вышеупомянутой паре чисел первое равно нулю и второе равно случайным образом выбранному номеру из множества , который при этом исключают из множества , инициализируют , случайным образом выбирают из множества элемент и ставят ему во взаимно однозначное соответствие элемент , определяя таким образом преобразование , выполняют проверку дистанционного разнесения перемеженных символов, для чего для всех таких, что , , вычисляют значение , если все полученные значения разные, то увеличивают значение , исключают элемент из множества и добавляют во множество пару , если хотя бы две разности оказываются равны, то повторно выбирают другой элемент из множества и повторяют для него проверку дистанционного разнесения перемеженных символов, при невозможности найти элемент, удовлетворяющий проверке дистанционного разнесения перемеженных символов, повторяют весь алгоритм заново с уменьшенным параметром разнесения , повторяют процедуру до тех пор, пока множество не станет пустым, а множество не будет содержать пар чисел, формируют перемеженные подпоследовательности, располагая элементы в соответствии с их новыми номерами в каждой подпоследовательности, используя пилотную псевдослучайную последовательность номеров, объединяют перемеженные подпоследовательности в первую перемеженную последовательность, в первой перемеженной последовательности выполняют второе перемежение, для чего для каждого символа в последовательности формируют его новый номер в последовательности по порядку путем выполнения преобразования вида , где - количество перемежаемых элементов, а - старый номер в первой перемеженной последовательности, - число взаимно простое с , формируют вторую перемеженную последовательность, располагая элементы первой перемеженной последовательности в соответствии с новыми номерами, для каждого -го элемента, начиная с первого, получают новый номер во второй перемеженной последовательности, где новый номер равен , при этом номера остальных элементов последовательности не изменяют, формируют третью перемеженную последовательность, располагая элементы в соответствии с их новыми номерами, отличающийся тем, что для первых K элементов в третьей перемеженной последовательности вычисляют функцию дистанционного разнесения перемежителя для каждого из первых K элементов, для чего для произвольного номера находят ; обратным преобразованием получают ; обратным преобразованием получают ; находят , обратным преобразованием получают ; обратным преобразованием получают ; находят ; обратным преобразованием получают ; обратным преобразованием получают ; сортируют вектор, составленный из индексов по возрастанию, получая сортированный вектор ; делают циклическую перестановку в векторе вида , получают вектор ; вычитают из вектора вектор , находят в результирующем векторе минимум по абсолютной величине, который и является значением функции дистанционного разнесения перемежителя для элемента с номером , определяют элементов с наименьшим значением этой функции, индексы которых осуществляют все возможные циклические перестановки элементов третьей последовательности, для которых выполняется таким образом, что , где , для каждой перестановки вычисляют функцию дистанционного разнесения для каждого из первых K элементов перемеженной третьей последовательности, выбирают в качестве четвертой перемеженной последовательности ту, где минимальное значение функции дистанционного разнесения максимально, определяют элементов с наименьшим значением этой функции и итеративно повторяют процесс оптимизации путем выполнения циклических перестановок и определения той перестановки, где минимальное значение функции дистанционного разнесения максимально до тех пор, пока не достигнут заранее заданного порога минимального значения функции дистанционного разнесения, формируя тем самым как последовательность циклических сдвигов длиной , каждый из элементов которой , где - номер итерации, так и финальную последовательность перемеженных символов.