Устройство для обнаружения ошибок в несистематическом сверточном коде

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)5 Н 03 M 13/12

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ . (21) 4471959/24 (22) 07,07.88 (46) 07,07.91. Бюл. № 25 (72) Б.M.Çëîòíèê (53) 621,391,256 (088,8) (56) Авторское свидетельство СССР

N 1580567, кл. Н 03 М 13/12, 29.03,89.

Авторское свидетельство СССР

¹ 1443180, кл. Н 03 M 13/12, 1987, (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ

ОШИБОК В НЕСИСТЕМАТИЧЕСКОМ

СВЕРТОЧНОМ КОДЕ (57) Изобретение относится к вычислительной технике и технике связи. Его использо»5U 1662012 А1 вание в системах передачи данных позволяет повысить достоверность декодирования и упростить устройство за счет сокращения числа операций. Устройство содержит блок 1 оперативной памяти, коммутирующий элемент 7, элемент ИСКЛЮЧАЮЩЕЕ

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

1662012

Изобретение относится к вычислительной технике и технике связи и может быть использовано в системах передачи данных, На фиг,2а — в показаны сигналы на выходах 18 — 20 блока 12 синхронизации соответственно.

В основе работы устройства лежит новый принцип аналитического представления любого информационного сигнала xj несистематическогЬ сверточного кода системой нелинейных уравнений xj = f (у ), где у, ук+1 — сигналы, образующие элементарный блок кода при скорости кода 1/2.

В общем случае информация передается последовательностью элементарных блоков с длиной кодового ограничения v, причем каждый элементарный блок состоит из и сигналов yi...„yi+n-1, Из полной системы уравнений для цели обнаружения ошибки и дешифрации кода выбирают два уравнения с наименьшим числом ! элементарных блоков, причем = г, .„, 21 -3. Для кодов со скоростью передачи

1/2, в которых элементарный блок образуют два сигнала ук. у +1 с длиной кодового ограничения v = 3 и 5, системы уравнений имеют вид

У + У!+1+ У +3 =Р:

Yk+4 + Yk+5 = 2

yk+2 + УК+3 + jjk+4 + Yk+6 + Yk+7 =Я

yk+7 + yk+8 + yk+9 =,!4

Xj=

v=3

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

На фиг.1 приведена функциональная схема устройства; на фиг.2 — выходные сигналы блока синхронизации; на фиг.3 — алгоритм работы устройства, Устройство содержит блок 1 оперативной памяти, формирователь 2 адресов записи, первый 3 и второй 4 ключевые

1 элементы, первый 5 и второй 6 счетные триггеры, первый 7 и второй 8 коммутирующие элементы, элемент ИСКЛ1ОЧА!ОЩЕЕ ИЛИ 9, элемент И 10„элемент 11 задержки, блок 12 синхронизации, счетчик

13 импульсов, дешифратор 14 и блок 15 постоянной памяти. На фиг,1 обозначены выход 16 ошибки, информационный выход

17, а также первый — третий выходы 18 — 20 блока 12 синхронизации, первые 21, второй 22, третий 23 и четвертый 24 выходы дешифратора 14.

10 xj=

v=5

yk + Угс+1 + У1+2 + jjk+4 + Уk+5 +

+ yk+6 + Yk+7 + в+8 + Yk+9 =ф

Yk + Y k+1 + jk+3 + jjk+5 + Yk+8 +

+ Yk+9 + Yk+11 + Yk+12 + Yk+13 /

yk+4+ У1+5+ Yk+7+ yk+8+ Yk+11 +

+ yk+12 + yk+14 + yk+15 + УК+17 + У! +18 +

+ Yk+19 /

УМ+6+ yk+7+ УМ+9+ УЕ+10+ Yk+13+

+ У1+14+ У1+15+ yk+17+ yk+18+ yk+20+

У!+21 =У4:

Yk+8 + У1+9 + УМ+11 + yk+12 + У1+14 +

+ У К+15

yk+8 + У1+9 + Yk+10 + Yk+12 + У1+13 +

+ УК+15 + yk+16 + уК+18 + jk+19 =Уб

yk+10 + Yk+11 + Yk+13 + Уk+19 + У1+20 +

+ yk+Z2 + yk+23 =Я;

Yk+12 + yk+13 + У1+14 + yk+15+ Уk+21 +

+ yk+22 + yk+23 =ф

20 Наименьшее число элементарных блоков охватывают пары уравнений: при v = 3 ",У,,Р и = 3, при v= 5,Я I = 6. Если v = 7, то I = 11, если v = 12, то I = 19, Два отобранных уравнения называют проверками и Обозначают

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

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

Яг = Xj + XI+1 + Х!+2 92 Xj + Xj+2, Операции обнаружения ошибок и дешифрации коДа выполняют следующим образом; запоминают I последовательных элементарных блоков принятой последо40 вательности у*; выбирают из них путем последовательного считывания сигналы

yk, ..., y>, входящие в проверки S1, S2; . проверяют на четность число единиц в сигналах у*, входящих в каждую провер45 ку; если число единиц четно, значение S1 или S2 устанавливают равным О, если число единиц нечетно, значение S1 или 52 устанавливают равным 1; после получений значений S1, S2 проверяют выполнение ра50 венства S1 = S2 = S; если равенство имеет место на v-1последовательных элементарных блоках, ошибок нет и значение информационного сигнала х* устанавливают равным значению S; если S1ФЯ2, сигнал

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

1662012

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

12 синхронизаций обеспечивает синфазное считывание сигналов с блока 1 памяти и дешифратора 14 для формирования проверок S1, 52.

Блок 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, соответствующие двум проверкам S1, Sz. Выходы триггеров 5 и 6 соединены через коммутирующие элементы 7 и 8 с элементами 9 и 10, При S1 A S2 элемент ИСКЛЮЧАЮЩЕЕЕ ИЛИ 9 возбуждает выход 16, формируя сигнал ошибки, если S1 = S2, элемент И 10 возбуждает выход 17, Элементами 7 и 8 управляют импульсы, подфазированные в элементе 11 задержки, Работу устройства рассмотрим на примере несистематического сверточного кода с длиной кодового ограничения 1 = 5 и скоростью кода 1!2. Предполагают,. что передана последовательность

Y = 0000011010i 101100000000..., а принята последовательность

Y* = 000000101000100000000000....

jJ -элементарный блок (ЭБ) 20

Символы Y* поступают в блок 1 в ячейки памяти с адресами О, 1, 2, ..., 11. причем левые символы ЭБ поступают раньше, чем правые. За интервал каждого ЭБ блока 12 синхронизации выдает 12 импульсов для формирования адресов считывания, которые в процессе работы счетчика 13 и дешифратора 14, а также блока 15 выдают в следующем порядке адреса считывания блока 1 и сигналы пропускания (П) и непропускания (Н) ключевых элементов 3 и 4.

Адреса считывания блока 1

О 1 2 3456789 10 11

Ключевые элементы 3

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

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

К концу интервала ЭБ триггеры 5 и 6 хранят результаты проверок S1, Sz, До записи в блок 1 ЭБ, содержащего первую единицу в последовательности Y*, триггеры 5 и 6 в конце каждого ЭБ хранят сигналы S1 = Sz = О. Импульс ЭБ на выходе 19 блока 12 считывает сигналы S1, S2 через элементы 7 и 8 и, так как S1 == Sz =- О, то на выходах 16 и 17 на интервале ЭБ появляются сигналы. со значением О.

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

У*, по адресам элементов 10 и 11 блока 1 к концу интервала ЭБ в триггере 5 хранится сигнал со значением О, в триггере 6 — сигнал со значением 1, на. выходе 17 — сигнал со значением О. Единичный сигнал на выходе

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

Высокая эффективность рассмотренного алгоритма проверена и подтверждена на сверточном коде со скоростью 1/2 и с длиной кодового ограничения v = 12, в котором две проверки S1, S2, охватывающие 19 элементарных блоков сигналов у, обнаруживали ошибки кратностью, превышающей гарантированную кратность в 14 ошибок.

Для того же, чтобы обнаружить ошибки любой, даже небольшой кратности по алгоритму

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

Формула изобретения

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

Фиг.Г а а оо оа а.

00 )=a

0 Рею

0 оыибог

00

Sr

87 уФ а а а

О а а

0 а о о

0 0 а

ОО 00 ао аа

Si 7

o o о а

0 Х

0 лют

0 о а

0 о а а

О обнаружена ошибка

0 Ю Е Е Е 0 0

Неопределенные

Зб 36 36 значения Л РигЗ

Составитель О. Ревинский

Техред M,Ìîðãåíòàë Корректор

С, Черни

Редактор Н, Рогулич

Заказ 2137 Тираж 458 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

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