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



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

 


Владельцы патента RU 2571605:

Открытое акционерное общество "Камчатский гидрофизический институт" (ОАО "КГФИ") (RU)

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

 

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

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

Известны способы кодирования/декодирования данных, обеспечивающие исправление как одиночных, так и кратных ошибок (см., например, [1], [5]). При передаче данных с М-арным кодированием [1, раздел 6.1.2.], представляющих собой блоки информационных P-разрядных символов (при P=log2M), ошибка, возникающая при детектировании 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, отличающийся тем, что каждая совокупность р-х разрядов избыточных символов определяется на передающей стороне совокупностью этих же р-х разрядов ряда К информационных символов, а результат декодирования каждого информационного символа на приемной стороне формируется с учетом совокупности р-х разрядов информационных и избыточных символов блока в соответствии с исправляющим кодом Хемминга.



 

Похожие патенты:

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

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

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

Изобретение относится к радиосвязи, реализуемой посредством каналов с частотной модуляцией сигналов. .

Изобретение относится к радиосвязи, реализуемой посредством каналов с частотной модуляцией сигналов. .

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

Изобретение относится к технике связи и вычислительной технике. .

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

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

Изобретение относится к технике связи и может быть использовано в системах передачи дискретной информации. Техническим результатом является повышение скорости декодирования и достоверности принимаемой информации. Способ содержит этапы, на которых: для всех разрешенных кодовых комбинаций произвольного блокового (n, k)-кода по любым 1<f≤k/2 разрядам определяют номер кластера в двоичном представлении при условии, что в совокупности все образцы номеров кластеров образуют полный набор элементов из поля GF(2f). Среди оставшихся n-f разрядов выбирают k-f разрядов так, чтобы в совокупности для всех комбинаций кластера на позициях этих разрядов оказался полный набор элементов поля GF(2k-f). Кластер с номером ноль принимается за базовый. Любая комбинация из состава других кластеров может быть приведена к одной из комбинаций базового кластера после вычисления номера ее кластера i≠0 и сложения с известной приемнику ключевой комбинацией Ki. Признаком комбинации Ki в кластере является наличие единичного элемента поля GF(2k-f) относительно операции сложения на позициях k-f разрядов. Точное определение номера кластера обеспечивается выделением любого разряда не вошедшего в число выбранных ранее k-f разрядов для проверки четности разрядов номера кластера на передаче и их итеративных преобразований на основе индексов мягких решений (ИМР) на приеме. После вычисления номера кластера его разряды временно из процедуры декодирования исключаются. Оставшаяся часть принятого вектора с использованием части Ki переводится в базовый кластер и упорядочивается по убыванию значений ИМР, формируя при этом вектор и матрицу перестановок Р. С использованием этой матрицы переставляются столбцы базового кластера, при этом обращают внимание на то, чтобы на позициях k-f старших разрядов образовался полный набор элементов из поля GF(2k-f). В случае необходимости одновременно переставляют ближайшие столбцы в кластере и в векторе . Из полученного набора выбирают ту строку кластера, которая на позициях k-f разрядов совпадает с битами в . Складывая этот вектор с , получают упорядоченный образец ошибок , который путем умножения на PT и возвращения разрядов номера кластера приводят к истинному вектору ошибок. 14 табл.

Изобретение относится к области кодирования/декодирования цифровой информации и может быть использовано в системах передачи информации. Техническим результатом является повышение достоверности передачи при обмене данными. Способ содержит представление на передающей стороне каждого блока данных, содержащего последовательность из K информационных P-разрядных символов, в виде P матриц, содержащих каждая по M строк и N столбцов, причем каждую матрицу компонуют из p-х разрядов информационных символов, добавляют к каждой матрице M+N избыточных (проверочных) бинарных символов, а на приемной стороне определяют номера строк и столбцов каждой матрицы, в которых обнаружены ошибки, определяют бинарный символ, являющийся общим для каждой из указанных строки и столбца, изменяют код этого бинарного символа на дополнительный, определяют символы, в которых произошли ошибки, причем каждый из таких символов определяется по той матрице, в которой ошибка обнаружена только в одном столбце и одной строке, а каждая из совокупности операций изменения кода каждого бинарного символа осуществляется над совокупностью бинарных символов, принадлежащих тем символам, в которых произошли ошибки. 1 ил.
Наверх