Устройство для обнаружения ошибок в несистематическом сверточном коде Советский патент 1991 года по МПК H03M13/23 

(Л

С

Изобретение относится к вычислительной технике связи. Его использование в системах передачи данных позволяет повысить достоверность декодирования и упростить устройство за счет сокращения числа операций. Устройство содержит блок 1 оперативной памяти, коммутирующий элемент 7, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 9, элемент И 10, блок 12 синхронизации и счетчик 13 импульсов. Благодаря введению формирователя 2 адресов записи, ключевых элементов 3, 4, счетных триггеров 5, 6, коммутирующего элемента 8, элемента 11 задержки, дешифратора 14 и блока 15 постоянной памяти в устройстве реализуется новый алгоритм. 3 ил.

о о

hO

о к

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

Цель изобретения - повышение достоверности декодирования и упрощение устройства за счет сокращения числа операций.

На фиг.1 приведена функциональная схема устройства; на фиг.2 - выходные сигналы блока синхронизации; на фиг.З - алгоритм работы устройства.

Устройство содержит блок 1 оперативной памяти, формирователь 2 адресов записи, первый 3 и второй 4 ключевые элементы, первый 5 и второй 6 счетные триггеры, первый 7 и второй 8 коммутирующие элементы, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 9, элемент I/I 10, элемент 11 задержки, блок 12 синхронизации, счетчик 13 импульсов, дешифратор 14 и блок 15 постоянной памяти. На фиг.1 обозначены выход 16 ошибки, информационный выход 17, а также первый - третий выходы 18-20 блока 12 синхронизации, первые 21, второй 22, третий 23 и четвертый 24 выходы дешифратора 14.

Нафиг.2а-в показаны сигналы на выходах 18-20 блока 12 синхронизации соответственно.

В основе работы устройства лежит новый принцип аналитического представления любого информационного сигнала xj несистематическогй сверточного кода системой нелинейных уравнений xj f (yk), где yk, ум-1 - сигналы, образующие элементар- ный блок кода при скорости кода 1/2. В общем случае информация передается последовательностью элементарных блоков с длиной кодового ограничения V, причем каждый элементарный блок состоит из п сигналов yi ун-п-1. Из полной

системы уравнений для цели обнаружения ошибки и дешифрации кода выбирают два уравнения с наименьшим числом I элементарных блоков, причем I v, ..., 2v-3. Для кодов со скоростью передачи 1/2, в которых элементарный блок образуют два сигнала yk, ум-1 с длиной кодового ограничения v 3 и 5, системы уравнений имеют вид

fyk + yk+1 + yk+з -f :

Xj Jyk+4 + Vk+5 fa;

V

fyk+4 + Vk+5 fy I Vk+2 + Vk+3 + yk+4 + yk+6 + yk+7 fy yk+7 + yk+8 + yk+9 $,

0 xj

5

Vk + yb+1 + yk+2 + Vk+4 + Vk+5 +

+ yk+6 + yk+7 + yk+8 + yk+9 #

yk + yk+1 + yk+3 + yk+5 + yk+8 +

+ yk+9 + yk+11 + yk+12 + yk+13 JЈ

yk+4 + yk+5 + yk+7 f yk+8 + yk+11 +

+ Vk+12 + УМ 14 + yk+15 + УМ-17 + УМ-18 +

+ yk+19 y

yk+6 + yk+7 + yk+9 + УМ-10 + yk+13 +

+ yk+14 + yk+15 + УМ-17 + yk+18 + УМ-20 +

УМ-21 $;

yk+8 + yk+9 + yk+11 + yk+12 + yk+14 +

+ УМ-15 Д;

yk+8 + yk+9 + УМ-10 + yk+12 + yk+13 +

+ yk+15 + УМ-16 + yk+18 + УМ-19 $

yk+10 + yk+11 + yk+13 + yk+19 + yk+20 +

+ yk+22 + УМ-23 Ј;

yk+12 + Yk+13 + yk+14 + yk+15 + УМ-21 +

+ yk+22 + УМ 23 Jg.

Наименьшее число I элементарных блоков охватывают пары уравнений: при v- 3,P2 и | 3, при1 5; I 6. Если v 7, то 1 11, если v 12, то I 19. Два отобранных уравнения называют проверками и обозначают Si, $2. На фиг.З для сверточного кода с длиной кодового ограничения v 3 приведены последовательности информационных сигналов и соответствующих им элементарных блоков: без ошибок у и с ошибками у, а также показаны операции обнаружения ошибок и дешифрации кода, х - последовательность дешифрованных символов. Последовательность у определяется двумя порождающими многочленами:

91 Xj + XJ+1 + Xj+2,- Q2 Xj + Xj+2.

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

yk Ур, входящие в проверки Si, 82;

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

х заменяют символом стирания Ј, фиксируя наличие ошибок. Выполнение (v - 1) - кратного равенства необходимого для повышения надежности дешифрации кода.

Устройство работает следующим образом.

Принимаемая последовательность у Элементарных блоков сигналов поступает в блок 1 оперативной памяти. Два проверочных уравнения в виде номеров позиций, в которых расположены ненулевые проверяемые сигналы, хранятся в блоке 15 постоянной памяти. Проверочные уравнения хранятся в виде прошивок ПЗУ по адресам, соответствующим номерам позиций проверок. Все адреса считываются последовательно в течение каждого интервала элементарного блока и начало считывания (проверки) определяется импульсом частоты следования элементарных блоков. Блок 12 синхронизации обеспечивает синфазное считывание сигналов с блока 1 памяти и дешифратора 14 для формирования проверок Si, 82.

Блок 12 синхронизации выдает последовательности тактовых импульсов на первый выход 18, импульсы с частотой следования элементарных блоков - на второй выход 19, импульсы адресов считывания - на третий выход 20 (фиг.2). Импульсы на выходе 19 обеспечивают запись входных данных в блок 1. Счетчик 13 ведет последовательный счет импульсов с выхода 20 до тех пор, пока дешифратор 14 после формирования последнего адреса считывания сбросит счетчик 13 в исходное состояние сигналом на четвертом выходе 24. Дешифратор 14 выдает на первые выходы 21 последовательность чисел-адресов считывания блока 15. Блок 15 выдает адреса считывания блока 1. Одновременно дешифратор 14 по выходам 22 и 23 управляет ключевыми элементами 3 и 4, которые направляют выходные данные блока 1 в триггеры 5 и 6, соответствующие двум проверкам Si, 82. Выходы триггеров 5 и 6 соединены через коммутирующие элементы 7 и 8 с элементами 9 и 10. При S1 S2 элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 9 возбуждает выход 16, формируя сигнал ошибки; если Si 82, элемент И 10 возбуждает выход 17. Элементами 7 и 8 управляют импульсы, подфазированные в элементе 11 задержки.

Работу устройства рассмотрим на примере несистематического сверточного кода с длиной кодового ограничения v 5 и скоростью кода 1/2. Предполагают, что передана последовательность

Y 00000110101101100000000..., а принята последовательность

Y 000000101000100000000000... . U -элементарный блок (ЭБ)

Символы Y поступают в блок 1 в ячейки

памяти с адресами 0, 1, 2 11. причем

левые символы ЭБ поступают раньше, чем правые. За интервал каждого ЭБ блока 12

5 синхронизации выдает 12 импульсов для формирования адресов считывания, которые в процессе работы счетчика 13 и дешифратора 14, а также блока 15 выдают в следующем порядке адреса считывания

0 блока 1 и сигналы пропускания (П) и непропускания (Н) ключевых элементов 3 и 4.

Адреса считывания блока 1 0123456789 10 11 5Ключевые элементы3

ППНППНППНН Н Н

4

ПППНППНППН П П К концу интервала ЭБ триггеры 5 и 6 0 хранят результаты проверок Si, 82. До записи в блок 1 ЭБ, содержащего первую единицу в последовательности Y, триггеры 5 и 6 в конце каждого ЭБ хранят сигналы Si 82 0. Импульс ЭБ на выходе 19 5 блока 12 считывает сигналы Si, 82 через элементы 7 и 8 и, так как Si 82 0, то на выходах 16 и 17 на интервале ЭБ появляются сигналы со значением 0.

После записи сигналов ЭБ, содержаще0 го первую единицу в последовательности

Y, по адресам элементов 10 и 11 блок 1 к

концу интервала ЭБ в триггере 5 хранится

сигнал со значением 0. в триггере 6 - сигнал

со значением 1, на выходе 17 - сигнал со

5 значением 0. Единичный сигнал на выходе

16 фиксирует обнаружение ошибки.

Высокая эффективность рассмотренного алгоритма проверена и подтверждена на сверточном коде со скоростью 1/2 и с дли- 0 ной кодового ограничения V- 12, в котором две проверки Si, 82, охватывающие 19 элементарных блоков сигналов у, обнаруживали ошибки кратностью, превышающей гарантированную кратность в 14 ошибок, 5 Для того же, чтобы обнаружить ошибки любой, даже небольшой кратности по алгоритму Витерби, необходимо в этом коде последовательно генерировать 2046 элементарных блоков для того, чтобы произвести сравне- 0 ние только с одним принятым элементарным блоком.

Формула изобретения Устройство для обнаружения ошибок в 5 несистематическом сверточном коде, содержащее блок оперативной памяти, блок синхронизации, счетчик импульсов, первый коммутирующий элемент, элемент И и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ выход которого является выходом ошибки устройства, отличающееся тем, что, с целью повышения достоверности декодирования и упрощения устройства за счет сокращения числа операций, в устройство введены ключевые элементы, элемент задержки, второй коммутирующий элемент, счетные триггеры, дешифратор, блок постоянной памяти и формирователь адресов записи, выходы которого соединены с первыми адресными входами блока оперативной памя- ти, информационный вход которого является входом устройства, первый - третий выходы блока синхронизации подключены соответственно к входу формирователя адресов записи, входу элемента задержки и счетному входу счетчика импульсов, выходы которого соединены с входами дешифратора, первые,второй,третий и четвертый выходы которого подключены соответственно к входам блока постоянной памяти,

S I I I I I I I I I I I I I I

управляющим входам первого и второго ключевых элементов и входу обнуления счетчика импульсов, выходы блока постоянной памяти соединены с вторыми адресными входами блока оперативной памяти, выход которого подключен к информационным входам первого и второго ключевых элементов, выходы которых соединены с входами одноименных счетных триггеров, выходы которых подключены к информационным входам одноименных коммутирующих элементов, выход элемента задержки соединен с управляющими входами коммутирующих элементов, первые и вторые выходы первого и второго коммутирующих элементов подключены соответственно к первым и вторым входам элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и элемента И, выход которого является информационным выходом устройства