Способ помехоустойчивого кодирования и декодирования цифровых данных

Способ помехоустойчивого кодирования и декодирования цифровых данных

Иллюстрации

Показать все

Реферат

Изобретение относится к области передачи цифровой информации и предназначено для применения в кодерах/декодерах систем цифровой связи.

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

Известны способы кодирования/декодирования данных, обеспечивающие исправление как одиночных, так и кратных ошибок (см., например, [1], [5]). При передаче данных с М-арным кодированием [1, раздел 6.1.2.], представляющих собой блоки информационных P-разрядных символов (при P=log₂M), ошибка, возникающая при детектировании P-разрядного символа, влечет за собой ошибки в определении от 1 до Р бит этого символа. (О терминологии. Процедура декодирования в общем случае состоит из двух фаз; в первой фазе осуществляется детектирование (т.е. декодирование без исправления ошибок; см., например, [1, раздел 3.1.2.]), а на второй - собственно исправление возникших при детектировании ошибок). Таким образом, при детектировании блока символов ошибка всего в одном символе приводит к множеству битовых ошибок. В этой ситуации, какие бы совершенные помехоустойчивые коды не использовались, они не могут гарантировать высокой достоверности приема. Основная причина - в резком снижении корректирующих способностей кодов при наличии множественных ошибок в блоке. Кроме того, с ростом количества возможных ошибок имеет место значительный рост вычислительной сложности декодирования с их исправлением.

Реализуемое в ситуациях наличия пакетов ошибок (появляющихся вследствие замираний, имеющих место при распространении сигналов в канале) перемежение символов (см., например, [6, с.317, 323]), не дает существенного эффекта даже при одиночных ошибках в детектировании символов, поскольку в такой ситуации все ошибки относятся к одному символу блока, и при перемежении символов эти ошибки в совокупность одиночных ошибок не трансформируются.

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

Наиболее близким по технической сущности к заявляемому объекту является способ помехоустойчивого кодирования и декодирования цифровых данных, в основе которого лежит так называемый «прямоугольный код» [7, с.33] (см. также [1, раздел 6.3.3.2]). Это способ рассматривается в качестве прототипа. Прототип предусматривает представление каждого из блоков передаваемого сообщения «…в прямоугольниках (m-1)×(n-1). Затем к каждой строке блока, состоящей из m-1 символов, добавляется проверка на четность, так что длина строки становится равной m символам. Аналогично, к каждому столбцу добавляется по одному проверочному символу… Таким образом, первоначальный прямоугольник из (m-1)·(n-1) двоичных символов превращается в массив из m·n двоичных символов». Далее в прототипе на приемной стороне посредством проверки на четность определяются строка и столбец, в которых имеется ошибка (если она вообще имеется), и конкретный ошибочный символ, являющийся для этой пары строки и столбца общим, т.е. находящийся на их пересечении. Исправление ошибки производится изменением кода этого символа на противоположный (с «1» на «0» или наоборот). В случае М-арного кодирования, т.е. представления каждого символа P-разрядным кодом реализация прототипа предполагает расположение разрядов каждого символа в строке или в столбце прямоугольника. При этом в случае ошибочного детектирования всего одного символа соответственно в строке или в столбце указанного прямоугольника будут иметь место ошибочно определенные биты этого символа (в количестве от 1 до Р штук). Тогда в случае четного количества указанных ошибочно определенных бит проверка на четность ошибок не выявит, и при этом прототип исправление ошибок не обеспечивает. Последнее имеет место с вероятностью ≈0.5.

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

Целью заявляемого способа является повышение достоверности передачи.

Цель достигается тем, что в способе помехоустойчивого кодирования и декодирования цифровых данных, состоящем в представлении на передающей стороне каждого блока данных, содержащего последовательность из K P-разрядных информационных символов, в виде прямоугольника и добавлении к этому блоку избыточных символов, а на приемной стороне - в декодировании каждого указанного блока с учетом составляющих его информационных и избыточных символов, разрядность каждого из избыточных символов составляет Р≥2, причем совокупность p-х разрядов избыточных символов определяется на передающей стороне совокупностью этих же p-х разрядов K информационных символов, а каждый p-й разряд результата декодирования каждого информационного символа на приемной стороне определяется с учетом совокупности p-х разрядов ряда информационных и избыточных символов блока.

Предусмотренный заявляемым способом принцип кодирования иллюстрируется следующим образом (на примере использования в нем исправляющего кода Хемминга). Пусть bkp - значение p-го бита k-го информационного символа, а βrp - значение p-го бита r-го избыточного (проверочного) символа (причем p=1…P, k=1…K, r=1…R). Тогда результат выполнения операции представления на передающей стороне системы связи каждого блока данных, содержащего последовательность из K P-разрядных информационных символов, в прямоугольниках имеет следующий вид:

При принятых выше обозначениях сформированный прямоугольник имеет размеры P×K.

Результат же выполнения операции добавления к блоку (1) информационных символов R P-разрядных избыточных символов, каждый p-й разряд каждого из которых определяется только совокупностью этих же p-х разрядов K информационных символов, имеет следующий вид:

Подробное описание выполняемой на передающей стороне процедуры вычисления избыточных символов для отдельной строки прямоугольника (блока) (2) применительно к ситуации использования исправляющего кода Хемминга приведено, например, в [5, раздел 9.2, с.179] со следующим уточнением: в настоящем описании, в отличие от [5], порядок расположения элементов в каждой строке блока (2) соответствует записи двоичных чисел в порядке убывания номеров разрядов справа налево. Процедуры вычисления R избыточных символов для всех P строк выполняются независимо друг от друга и алгоритмически полностью совпадают. В итоге выполнения указанной операции сформирован прямоугольник (блок) P×(K+R).

Выполняемая на приемной стороне операция определения каждого p-го разряда результата декодирования каждого информационного символа bkp с учетом совокупности p-х разрядов ряда информационных и избыточных символов блока также подробно описана в [5, раздел 9.2]. В итоге выполнения этой операции формируется прямоугольник (1) (т.е. при декодировании исправляются все потенциально имеющиеся в блоке ошибки) при выполнении одного из следующих условий:

- в каждом передаваемом блоке имеет место ошибка в детектировании не более чем одного символа;

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

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

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

В связи с тем, что малым размерам блоков соответствует значительное относительное (в сравнении с этим размером) количество необходимых проверочных символов (что влечет за собой существенное снижение скорости передачи данных вследствие применении помехоустойчивого кодирвоания), представляют интерес ситуации, при которых необходимое для исправления одной ошибки количество избыточных символов при использовании кода Хемминга составляет не менее R=5. В этих ситуациях количество информационных символов в блоке составляет до K=26, и тогда потери скорости передачи вследствие применения помехоустойчивого кодирования составляют всего 20%.

Достигаемый в заявляемом способе технический эффект повышения эффективности кодирования/декодирования (т.е. достоверности передачи данных) обусловлен тем, что вместо реализуемого в прототипе добавления к каждой строке и столбцу прямоугольника (блока) по одному биту проверки на четность в заявляемом способе осуществляется добавление ко всей таблице совокупности из R (≥5) проверочных P≥2 - разрядных символов, а вместо имеющего место в прототипе определения ошибочного бита (как «точки пересечения» содержащих выявленную ошибку строки и столбца) в заявляемом объекте исправление ошибок реализуется поразрядным (т.е. индивидуально для каждого разряда информационных символов каждого блока).

Литература.

1. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. 2-е издание. М.: Издательский дом «Вильяме». 2003.

2. Брауде-Золотарев Ю.М., Лаврентьев М.А. Способ помехоустойчивого кодирования и декодирования. Патент РФ №2214678.

3. Брауде-Золотарев Ю.М., Грибань С.В. Способ помехоустойчивого кодирования и декодирования. Патент РФ №2213416.

4. Смирнов О.В., Вергелис Н.И. Декодер с обнаружением и исправлением ошибок. Патент РФ №2370887.

5. Липкин И.А. Статистическая радиотехника. Теория информации и кодирования. М.: Вузовская книга, 2002.

6. Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. Вып. 28. М.: Радио и связь. 1987.

7. Хемминг Р.В. Теория кодирования и теория информации. М.: Радио и связь, 1983.

1.. Способ помехоустойчивого кодирования и декодирования цифровых данных, состоящий в представлении на передающей стороне каждого блока данных, содержащего последовательность из К≥2 Р-разрядных информационных символов, в виде прямоугольника и добавлении к этому блоку R≥5 избыточных символов, а на приемной стороне в декодировании каждого указанного блока с учетом составляющих его информационных и избыточных символов, отличающийся тем, что разрядность каждого из избыточных символов составляет Р≥2, причем совокупность р-х разрядов избыточных символов определяется на передающей стороне совокупностью этих же р-х разрядов К информационных символов, а каждый р-й разряд результата декодирования каждого информационного символа на приемной стороне определяется с учетом совокупности р-х разрядов информационных и избыточных символов блока.

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