EA009629B1

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

Info

Publication number: EA009629B1
Application number: EA200601381A
Authority: EA
Inventors: Алексей Владимирович Домашев; Андрей Юрьевич ЩЕРБАКОВ; Евгений Александрович Дуйков; Сергей Вячеславович Сотский
Original assignee: Некоммерческая Организация «Фонд Сопровождения Инвестиционных Проектов "Генкей"»
Priority date: 2006-06-21
Filing date: 2006-06-21
Publication date: 2008-02-28
Also published as: EA200601381A1

Abstract

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

Description

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

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

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

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

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

Так, например, широко известен код БЧХ (5,15,7) (см. «Коды и математика», авторы М.Н. Аршинов, Л.Е. Садовский, издательство «Наука», 1983 г., с. 73), где

- длина блока двоичной информации в битах;

- длина кодового слова;

- минимальное расстояние кода.

Порождающей матрицей данного кода является

	(\	1	1	0	1	1	0
	0	1	1	1	0	1	1
с-	0	0	1	1	1	0	1
	0	0	0	1	1	1	0
	А	0	0	0	1	1	1

О 1 0 1 О О О (Г

0 1 0 1 0 0 0

0 10 10 0

110 0 10 10 0 110 0 10 1,

Кодирование происходит путем разбиения исходной информации на блоки по 5 бит и их умножения на матрицу С, в результате чего получается кодированная информация длиной 15 бит, в которой затем можно исправлять любые ошибки, вес которых не больше 3 (т. е. ошибки в любых трех или меньшем числе позиций).

Легко рассчитать, что при передаче информации, таким образом, необходимо вместо 5 бит передавать ровно в три раза больше, что означает избыточность при передаче или хранении информации, равную 200%, что неприемлемо, в первую очередь, для низкоскоростных каналов связи.

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

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

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

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

По предлагаемому способу кодирования к информационному блоку М длиной т вырабатывается

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

К=Н(М)

Передача информации организована таким образом, что для каждого блока М₁ вычисляется контрольный блок К₁=Н(М₁), который объединяется с М₁, образуя помехоустойчивый блок М₁||К₁, который передается в канал связи.

В канале связи действуют ошибки, которые моделируются следующим образом - переданный помехоустойчивый блок М₁||К₁ суммируется по модулю 2 с вектором ошибки О веса ΐ и длиной т+к.

Далее декодирование полученного потенциально искаженного ошибкой помехоустойчивого блока производится следующим образом - перебирается все множество возможных ошибок, называемых также синдромами, веса ΐ и для каждого синдрома 8* вычисляется Н(М₁+О+8_4х) и сравнивается с К₁, в случае, если ошибки не приходятся на корректирующий блок, и с К₁+[8_4х] в противном случае (|8,_х| - последние т бит вектора синдрома).

При совпадении фиксируется, что ошибка вызвана синдромом 8,, и она исправляется суммированием по модулю 2 с этим синдромом на длине т информационного блока.

При этом мощность множества синдромов определяет трудоемкость декодирования и оценивается сверху величиной О=(т+к)'.

Возможная ошибка декодирования, при которой искаженный вектор может быть принят за правильный, оценивается величиной р=Э/2^к.

Технически целесообразно оценивать параметр ΐ величиной 2-3 и, исходя из этого, варьировать длину информационного блока т.

В реализации заявленного способа в описываемом ниже макете, реализующем телефонную связь повышенного качества, ΐ=1 и ΐ=2, длина информационного блока т=64 байта=512 бит, длина контрольного блока к=4 байта=32 бита, избыточность порядка 6% и достоверно исправляются 2 ошибки на блок.

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

существенное снижение избыточности информации при помехоустойчивом кодировании (с сотен процентов до 5-10%);

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

адаптивное изменение параметров кодирования в зависимости от практической надобности.

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

Телефонный аппарат содержит приемо-передающую антенну 1 телефона, приемо-передающее устройство 2, интерфейсный блок 3, вычислительный узел 4 с микропрограммой кодирования и декодирования, запоминающее устройство 5 для временного хранения данных, генератор 6 корректирующих блоков, блок 7 восстановления речи, устройство 8 воспроизведения речи, вокодер 9 и микрофон 10. Элементы 3-6 телефонного аппарата программным образом реализуют заявляемый способ.

Каждый из телефонов, содержащий устройство для кодирования и декодирования (интерфейсный блок 3, вычислительный узел 4, запоминающее устройство 5, генератор 6 корректирующих блоков), обменивается с другим телефоном речевой информацией, вводимой с микрофона 10, преобразуемой в цифровую форму вокодером 9, передаваемой в интерфейсный блок 3, который разбивает на информационные блоки представленную в двоичном коде речевую оцифрованную информацию, далее для каждого полученного таким образом информационного блока в вычислительном узле 4 вычисляют функцию, зависящую от каждого бита информационного блока, в качестве которой используется имитовставка, в результате вычисления функции получают контрольный блок, который направляется обратно в интерфейсный блок 3, в котором объединяют результат вычисления функции с исходным информационным блоком, в результате чего образуется помехоустойчивый блок, содержащий кодированную цифровую информацию, который затем направляется на приемо-передающее устройство 2, которое в свою очередь передает его на приемо-передаюшую антенну 1 телефона и направляет его другому телефону по радиоканалу.

Принимаемая от другого аналогично устроенного телефона с номером _) цифровая информация, состоящая из помехоустойчивого блока, содержащего информационный и контрольный блоки, составляющие кодированную цифровую информацию, поступает из радиоканала на приемо-передаюшую антенну 1 телефона ί, затем на приемо-передающее устройство 2, передается в интерфейсный блок 3, который выделяет из нее информационный блок, после чего каждый выделенный информационный блок направляется в вычислительный узел 4, в котором для упомянутого блока вычисляют функцию, зависящую от каждого бита информационного блока, в качестве которой используется имитовставка, далее в этом же вычислительном узле 4 сравнивают вычисленное значение функции с её же ранее вычисленным значени

- 2 009629 ем, составляющим контрольный блок, при совпадении значений информационный блок расценивают как декодированную цифровую информацию и направляют данную цифровую информацию, являющуюся оцифрованной речью, в блок восстановления речи 7, а затем в устройство 8 воспроизведения речи. При несовпадении значений последовательно при помощи генератора 6 корректирующих блоков изменяют по меньшей мере несколько бит помехоустойчивого блока, таким образом получая скорректированный помехоустойчивый блок, и далее в вычислительном узле 4 вычисляют для каждого скорректированного помехоустойчивого блока, размещенного в запоминающем устройстве 5 для временного хранения данных, упомянутую функцию и сравнивают её с ранее вычисленным значением, составляющим контрольный блок, при совпадении значений скорректированный информационный блок расценивают как декодированную цифровую информацию и направляют декодированную цифровую информацию, являющуюся оцифрованной речью, в блок восстановления речи 7, а затем в устройство воспроизведения речи 8.

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

Claims

ФОРМУЛА ИЗОБРЕТЕНИЯ

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