Способ декодирования информации с использованием свёрточных кодов Российский патент 2017 года по МПК H03M13/23 H03M13/43 

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

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

Известен способ декодирования в системе помехоустойчивого кодирования сигналов в цифровой системе радиосвязи [RU 2573263, C2, Н03М 13/15, Н03М 13/23, 20.01.2016], путем преобразования входного сигнала в цифровой вид с помощью дельта-модуляции, заключающийся в том, что цифровое значение е_i, очередного i-го отсчета определяется разностью между отсчетом входного сигнала x_i и формируемой аппроксимацией этого отсчета y_i, выраженной зависимостью:

,

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

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

Наиболее близким по технической сущности к предложенному способу является способ порогового декодирования в системе помехоустойчивого кодирования, который реализуется пороговым декодером, представленным фиг. 3 [В.В. Золотарев, Г.В. Овечкин. Помехоустойчивое кодирование. Методы и алгоритмы. Справочник. М., "Горячая линия - телеком", 2004, 124 с., с. 80], заключающийся в том, что после передачи по каналу связи информационные символы кода (поток U) направляют в информационный регистр, а проверочные символы (поток V) - в синдромный регистр, используя пороговый элемент (ПЭ), являющийся решающим элементом декодера, суммируют определенные символы синдрома (проверки) и, если число ненулевых символов на входе ПЭ превышает заданное пороговое значение, то изменяют содержимое ячеек, с которых снимались сигналы, а также декодируемый символ в шестой ячейке информационного регистра.

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

Задача, которая решается в изобретении, направлена на повышение эффективности декодирования при высоком уровне шума.

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

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

На чертеже представлены:

на фиг. 1 - кодер дивергентного кода;

на фиг. 2 - дивергентный декодер;

на фиг. 3 - декодер, реализующий способ-прототип.

На чертежах обозначены: 0…n - ячейки регистров, ПЭ - пороговые элементы.

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

Представим возможности предложенного дивергентного способа декодирования в системе помехоустойчивого кодирования с постепенно растущими ("расходящимися") значениями кодового расстояния d при увеличении длины регистров декодера. Для этого рассмотрим вначале схему простого сверточного кодирования с кодовой скоростью R=1/2, представленную на фиг. 1.

Это простой обычно используемый кодер сверточного кода, в котором одна крайняя правая связь ячейки с полусумматором, который определяет конкретный вид кодера, находится далеко справа от основной группы проверок.

Соответствующий ему вариант декодера, который является частью системы кодирования, представлен на фиг. 2.

Декодер работает следующим образом. В верхний сдвиговый регистр поступают слева информационные символы кода из канала, а в нижний - проверочные символы кода. Первый пороговый элемент ПЭ1 принимает решение о том, надо ли исправлять очередной контролируемый им информационный символ. Причем, такое решение может приниматься раньше, чем все символы кода поступят в декодер. Далее после того, как уже и последний крайний символ кода поступил в декодер, второй пороговый элемент ПЭ2 также декодирует контролируемые символы, но уже на основании большего на 1 или на 2, 3… числа проверок, если используется пороговый элемент, или на основании анализа всего кода, а не его части. При этом ПЭ1 облегчает работу ПЭ2, так как исправляет часть ошибок, которые пришли из канала. Одновременно ПЭ2, со своей стороны, также помогает ПЭ1, поскольку, как видно из фиг.2, крайняя правая проверка ПЭ2, участвующая в принятии решений, уменьшает число ошибок в нижнем регистре, называемом синдромным. Но именно это уменьшение вторым пороговым блоком ПЭ2 числа ошибок помогает первому пороговому блоку ПЭ1 улучшить свои решения, поскольку он в этом случае работает в более легких условиях. Получается, что оба пороговых элемента работают, как бы, при положительной обратной связи друг на друга (помогая друг другу), причем разные АЭ могут отличаться не одной проверкой, а несколькими.

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

На фиг. 2 показан декодер сверточного кода, соответствующий кодеру на фиг. 1. Он входит в систему кодирования и содержит 2 пороговых элемента (ПЭ1 и ПЭ2), находящихся в левой и правой частях декодера. ПЭ1 и соответствующие части информационного и синдромного регистров, с которыми он взаимодействует, выделены как Decoder1.

Полный декодер со вторым пороговым элементом ПЭ2 в правой части регистров декодеров подобен Decoder1. Но на вход ПЭ2 поступает еще и дополнительная дальняя проверка кода, которая появляется в декодере намного позже символов компактной группы проверок, связанных с первым пороговым элементом ПЭ1. Как уже отмечалось, их может быть и несколько.

Предложенный способ декодирования информации с использованием сверточных кодов с учетом предварительных разъяснений используется следующим образом. Первый пороговый элемент ПЭ1 получает из канала связи кодовые символы и принимает решения об информационных ошибках на основании только своей группы проверок. Если шум канала и код выбраны правильно, то после первого порогового элемента ПЭ1 плотность таких ошибок будет меньше, чем до него или другого активного элемента, а достигнув второго порогового элемента ПЭ2, число этих ошибок будет еще немного уменьшено. А поскольку на входы второго порогового элемента ПЭ2 поступает на одну проверку больше, чем их число в первом пороговом элементе ПЭ1, то и корректирующие возможности второго порогового элемента ПЭ2 будут более высокими, что позволит усилить процесс коррекции, так как второй пороговый элемент ПЭ2 работает с кодом, у которого минимальное кодовое расстояние d как бы выросло на единицу по сравнению с первым пороговым элементом ПЭ1. Это свойство некаскадного роста кодового расстояния удобно назвать дивергентностью, а метод декодирования дивергентным. Важно, что этого удалось добиться без привлечения методов каскадирования, которые отнимают избыточность у первого кода (и первого порогового элемента ПЭ1), что заметно уменьшало бы корректирующие возможности первого узла коррекции ошибок.

Очевидно, что предложенный способ, реализуемый схемой на фиг. 2, сам может быть первой частью системы помехоустойчивого кодирования с еще более длинными кодами с подобной же структурой. Тогда на двух таких условных "каскадах" кодирования/декодирования минимальное кодовое расстояние d уже будет увеличено на 2 или больше и т.д.

Предложенный способ требует настройки параметров системы кодирования. Рассмотрим пример выбора параметров такого способа декодирования при условии введения дополнительно в декодер на фиг. 2 разностного регистра, расположенного, например, над информационным регистром, как это требуется для правильной работы алгоритма декодирования, и назначим параметры кодирования для гауссовского канала при кодовой скорости R=1/2 и полном кодовом расстоянии всего кода d=7, когда первый пороговый элемент ПЭ1 имеет на входе только 5 проверок из синдромного регистра, тогда как у второго порогового элемента ПЭ2 их будет на одну больше, т.е. 6, а еще одна проверка для обоих пороговых элементов будет выбираться из соответствующих ячеек разностного регистра. Пусть код относится к обычным самоортогональным, а самая крайняя проверка будет на расстоянии не менее длины левого кода, с которым работает первый пороговый элемент ПЭ1. Это значит, что в кодере на полусумматор поступает содержимое 6 ячеек с номерами: 0, 1, 6, 25, 34, 70, причем, номер 6-й ячейки 70 более, чем вдвое, больше номера предыдущей ячейки 34. Это весьма важно и сделано для уменьшения группирования ошибок на обоих пороговых элементах при большом уровне шума, когда наиболее важно получить улучшение характеристик.

Компьютерное моделирование с настройкой пороговых элементов такой несложной для реализации схемы кодирования/декодирования показало, что предложенный способ позволяет работать при уровне шума на 0,2 дБ большем, чем в случае применения только одного порогового элемента ПЭ1.

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

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

Данный способ декодирования в системе помехоустойчивого кодирования можно рассматривать, как дальнейшее развитие новых методов коррекции ошибок на основе оптимизационной теории (ОТ) помехоустойчивого кодирования, изложенной Заявителем в монографии, изданной Международным союзом электросвязи (МСЭ/ITU) в Женеве в юбилейном для МСЭ 2015 году: V.V. Zolotarev, Y.b. Zubarev, G.V. Ovechkin. Optimization Coding Theory and Multithreshold Algorithms. // Geneva, ITU, 2015, 159 p. (http://www.itu.int/pub/S-GEN-OCTMA-2015).

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

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