Устройство для декодирования блочных кодов, согласованных с многопозиционными сигналами

 

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

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

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

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

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

Н А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР

1 (21) 4370501/24-24 (22) 07,12.87 (46) 15.02.90. Бюл. и б .(71) Институт проблем передачи информации АН СССР. (72) А.С,Данилин, В.А,Зиновьев, В.В.Зяблов, Д.Л.Коробков, С,Н,Лицын и С.Л.Портной (53) 681.325:621.394,14(088,8) (56) Зарубежная радиоэлектроника, 1985, п.7, с. 3-26.

Авторское свидетельство СССР по заявке Ю 4236863/24, кл. Н 03 М 13/00, 19.03,87.

Авторское свидетельство СССР по заявке М 4 158884/24, кл. Н 03 M 13/00, 1986. (и) ЯО(и) 1 5435 2

2 (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ

БЛОЧНЫХ КОДОВ, СОГЛАСОВАННЫХ С МНОГОПОЗИЦИОННЫМИ СИГНАЛАМИ (57) Изобретение относится к вь.числительной технике и технике связи. Его использование в системах передачи информации позволяет повысить помехоустойчивость устройства и точность декодирования, Устройство для декодирования содержит преобразователь 1 скорости поступления символов и 11 ступеней 3 декодирования, каждая из которых включает блок 4 памяти, кор ректор 5 сигналов, декодер б внутреннего кода, декодер 7 внешнего кода и блок 8 сравнения. Благодаря специфическому выполнению в каждой ступе3 1543552 4

55 ни Э декодирования декодера 7 внешнего кода, а также введению синхронизатора осуществляется последовательное декодирование вложенных кодов, ь ! .Изобретение относится к вычисли1

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

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

На фиг.1 представлена блок-схема устройства, на фиг.2-7 - схемы соответственно блока очередности стираний, блока объединения сигналов, уз а суммирования, блока выбора номера

Минимального числа, компаратора и синхронизатора, на фиг,8 - временные диаграммы работы устройства, на фиг.9 - пространство сигналов внутрейнего кодирования, Устройство содержит (фиг.1) преобразователь 1 скоростей поступления символов, синхронизатор 2 и N ступеней 3 декодирования (N — число внеш,них кодов во входном сигнале}, каждая из которых включает блок 4 па,мяти, корректор 5 сигналов, декодер 6 внутреннего кода, декодер 7 внеш него кода и блок 8 сравнения. На фиг.1 обозначены также информационные входы 9, вход 10 синхронизации и выходы 11. В описании приняты следующие обозначения: I, — разрядность J символов j ro (j = 1 N) внешнего ко да)(п. К1 Д ) где и К> и d) — соответственно общее число символов, число информационных символов и хэммингово расстояние j-го кода

I. = M; N — число бит надежности, Х, "1

1 = ) 1og n, где à — ближайшее большее целое, = ) 1.ор (Т + 1), Т (Pd /? ), где 1 — целая часть л числа, . = ь + 1.

J декодер 1 .j внешнего кода в j-й ступени З.j декодирования содержит (фиг.1) блок 12 очередности стираний, блок 13 анализа стираний, блок 14 сравнения лс каторов, переключатель

15, блок 16 памяти жестких символов, блок 17 памяти надежностей, блок 18 памяти стираний, блок 19 декодировапричем каждое из декодированных слов предыдущего кода корректирует информацию, подлежащую дальнейшему декодированию. 3 э.п. Ф-лы, 9 ил. ния, блок 20 объединения сигналов, блок 21 оперативной памяти, блок 22 суммирования, блок 23 выбора номера минимального числа и мультиплексор 24.

5лок 12 очередности стираний образуют (фиг.2} коммутаторы .25, буферные регистры 26 и элемент И 27. На фиг.2 обозначены также выходы 28.

Блок 13 анализа стираний представляет собой набор элементов сравнения, каждый из которых имеет выходы "Больше или равно" и "Меньше, Блок 14 сравнения локаторов представляет собой группу элементов равнозначности, выходы которых соедине ны с входами элемента ИЛИ. Первые входы элементов равнозначности образуют информационные входы блока, вторые их входы объединены и являют" ся управляющими входами блока.

Блок 16 памяти жестких символов, а также блок 18 памяти стираний и блок 21 оперативной памяти выполнены на оперативных запоминающих устройства (ОЗУ) .

Блок 17 памяти надежностей выполнен на 03У, выходы которого, являющиеся первыми выходами блока, подключены к входам преобразователя кодов, выполненного на программируемом постоянном запоминающем устройстве (ППЗУ), выходы которого являются вторыми выходами блока. Преобразователь

Формирует из сигнала а сигнал Ь = (6; — а) где h - минимальное

У

) евклидово значение системы сигналов на j-м шаге декодирования, Блок 19 декодирования обеспечивает направление ошибок и стираний и выполнен аналогично известному.

Блок 20 объединения сигналов содержит (фиг.3) первый и второй элементы ИЛИ 29, первый и второй элементы И 30, группу источников 31 постоянного кода, каждый иэ которых генерирует коды чисел 1, 2. ..,, Т + 1, группу элементов 37 равнозначности и группу элементов ИЛИ

5 15435

Блок 22 суммирования состоит из однотипных на кали вающих сумматоров, каждый- из которых содержит (фиг.4) сумматор 34 и буФерный регистр 35.

Входы 000 001 010 011 100 101 110 111

Выходы 11 01 10 01 11 00 10 00

Предположим, что к началу j-го ша15 га Декодирования уже найдены векторы а (... °, а (> 1. Далее внутренним кодом X, декодируется каждый столбец матриц В., В результате получаются вектор а с Х и число Ь ())

1 1

20 характеристика надежности, равная квадрату кодового расстояния от принятого слова до ближайшего в ансамбле Х>, если оно меньше 52, и равная в противном cl1óNàå (зависимость

) между надежностью и ее характеристикой обратная), Затем осуществляется декодирование вектора внешнего кода а = (аФ, ..., a(„ 1) эа Т + 1 по"

1 пыток, где Т j < f d /2 . В S-й попытЗ0 ке (S = 1,Т +1) декодируется вектор а 1 со стертыми 2(S-1) наименее. надежными символами, Пусть а ) (S) результат такого декЬдирования. Ему можно поставить в соответствие число

Блок 23 выбора номера минимального числа аналогично известному и содержит (фиг .5) компараторы 36, соеСинхронизатор 2 содержит (фиг.7) генератор 40 тактовых импульсов, первый и второй счетчики 4 1 и 42 с модулями соответственно N и и, блок -43 выделения синхрониэирующих меток, умножитель 44 частоты на 4-, первый — третий дешифраторы 45 чисел соответственно О, и+1 и ?п+1, первый и второй триггеры 46, элемент ИЛИ-НЕ

47, группу счетчиков 48 с модулями

Т + 1 и группу умножителей 49 частоты на Т . + 1. На фиг.7 обозначены первый-третий, четвертые и пятый выходы 50-54, а также первая и вторая группы 55 и 56 выходов.

Преобразователь 1 скорости поступления символов выполнен на ОЗУ. Блок

4.j памяти также выполнен на ОЗУ.

Корректор 5.j сигналов может быть реализован на ППЗУ или сумматоре. Декодер 6.j внутреннего кода представляет собой ППЗУ, реализующее алгоритм декодирования по максимуму правдоподобия в ансамбле сигналов Х

Устройство для кодирования, сопряженное рассматриваемому устройству для декодирования, а также канал связи идентичны известным. При этом на выходах канала связи (входах устройства для декодирования) формируются символы жесткого решения (M старших разрядов) и надежности (W младших разрядов).

Рассматриваемое устройство реалиЮ ° зует следующий алгоритм декодирования, являющийся обобщением алгоритма известного устройства.

IlycTt В = // P рl lH =1 Я я11

К = 1, Э,, И, h = 1, 4 (N+W), 1 =

1,и, — матрицы переданного и принятого (подлежащего декодированию) слова выбранной сигнально-кодовой конструкции (СКК), Декодирование про" водится за N шагов (ступеней), на каждом из которых находится слово а(11 6 А; внешнего кода А .

52

6 диненные по пирамидальной схеме, и вычислитель 37 возможной ошибки. Компаратор 36, как в известном устройстве, выполнен (фиг.6) на элементе 38 сравнения и элементе 2И-ИЛИ 39. Вычислитель 37 возможной ошибки выполнен на ППЗУ, которое реализует следующий алгоритм (для Т = 3):

Т (S) =,7 t (S, 1), где произвольЯ

Р-1 ный член суммы равен Q "-(j),.если .:

1-й символ j-го внешнего кода ошибочен и не стерт, и равен (Ь - Ь (j))2 в противном случае.

В качестве декодированного слова

j-го кода выбирается а(1 (S) с минимальным Т("(S). Для j-ro шага декодирования это слово является выходным и используется для коррекции матрицы (как в известном устройстве), после чего осуществляется переход к (j+1)му шагу.

Теория- показывает, что если находиться в пределах корректирующей способности СКК (расстояние от вектора шума до переданного вектора меньше

D /4), то принятое слово всегда де" кодируется верно.

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

1543552

На входы 8 устройства поступает последовательность иэ n сигналов, каждому из которых соответствует М бит жесткого решения (жестких бит) и W бит надежности. Эти сигналы за.писываются в преобразователь 1 ско рости - ОЗУ емкостью (И+И)),п — с частотой F. с которой ойи поступают из канала связи, а считываются с частотой F в виде кодовых слов внутреннего кода СКК. В результате на выходе преобразователя 1 образуется матрица В = )(P 1,< tt жестких сигналов с ошибками и их надежностей, причем для каждого элемента при фиксированном 1 первые 1 И сигналов соответствуют жесткому значению сигнала, а остальные !О W сигналов отвечают надежности, Эта матрица в 20 первой ступени 3.1 декодирования запоминается в блоке 4.1 памяти емкостью (М + W) х 3п на время 3а тактов частоты F — время декодирования слова первого внешнего кода. Одновре менно каждый столбец матрицы В посЪ тупает в декодер 6.1 внутреннего ко" да, в котором определяются номер подкода (поступающий на первый Ь! -раз, рядный выход) и надежность (поступаю- ЗО щая на второй W-разрядный выход), Работа этого блока иллюстрируется на фиг ° 9 °

Затем каждый из этих сигналов, составляющих слово из и символов, пос,тупает в декодер 7.! внешнего кода, на выходах которого в результате об,работки формируется первый вектор ошибки, который в блоке 8.1 сравнения сопоставляется с задержанной первой 4О строкой входной матрицы Pi. Результатом этого сопоставления является информационное слово первого внешнего кода на выходах 11.1. Одновременно тот же вектор ошибки используется в 45 корректоре 5.1 сигнала для исправлеА ,ния первой строки матрицы В.

Далее такой процесс последовательно повторяется в дальнейших ступенях

3 декодирования. В конечном счете на выходах 1! образуется N информационных слов, близость которых к исходным словам (на передаче) определяется эффективностью предлагаемого обобщенного алгоритма декодирования.

Рассмотрим обработку сигналов в произвольном декодере 7.j.

Символы надежностей, поступившие на входы декодера 7.j, подаются в блок 12 очередности стираний, внутри которого в четных регистрах 26 хранятся значения 2Т наименьших надежJ ностей в информационном блоке иэ п символов и их адреса в этом блоке в порядке возрастания надежностей, С. приходом каждого нового сигнала сначала он ставится на полагающуюся ему позицию, так что к концу информационного блока в блоке 12 образуются в возрастающем порядке 2Т самых нена-. .! дежных сигналов и их адреса °

Полученные в блоке 12 текущие 2Т! значения надежностей с его вторых выходов 28.2 подаются в блок 13 анаI лиза стираний, где с ними сравниваются надежности каждого сигнала, поступающего на входы блошка 13. На его вы" ходах вырабатывается управляющий сигнал, указывающий, нужно ли вставлять данный текущий сигнал куда-либо в середину списка из 2Т самых неJ надежных сигналов, или же его. надежность выше всех этих 2т надежностей

В записанных в четных регистрах 26 блока 12.

Сформированные в блоке 12 адреса надежностей (называемые далее локаторами) с его первых выходов 28.1 поступают одновременно в блок 14 сра внения локаторов и на переключатель 15.

В блок 15 поступает также на его управляющие входы сигнал D с выходов

53 синхронизатора 2. За и тактов в нем формируется информационный блок, имеющий "О" на позициях,, где стираний нет, и "1" в позициях со стираниями, Этот информационный блок поступает в блок 18 ОЗУ, где записывается с частотой F, a,ñ÷èòûBàåòñÿ с парциальной частотой Р .

В то же время переключатель 15 по очереди (по командам парциального управляющего сигнала С„) пропускает локаторы О, 2, 4. ..,, 2Т. в соответ„J ствии с (Т +1) -й попыткой декодиро) вания.

Поступающие на Ь -разрядные входы

J декодера 7. j жесткие .символы записываются в блок 16 по разрешению сигнала A с частотой F., а считываются с частотой F

Считанные жесткие символы одновременно с локаторами поступают в блок б

19 декодирования, в котором исправляются ошибки и стирания. Результаты декодирования в виде векторов ошибки

1543552

10 мультиплексора 24, на выходы которого пропускается соответствующий вектор 25 ошибки, Формула изобретения

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

35 блок памяти, декодер внутреннего кода, декодер внешнего кода, блок срав- 40 нения и корректор сигналов, N-я ступень декодирования содержит блок памяти, декодер внутреннего кода, деко" дер внешнего кода и блок сравнения, первые выходы декодера внутреннего кода j-й ступени декодирования (j = 1,N). соединены с первыми информа ционными входами декодера внеш"

45 него кода, выходы которого подключены к первым входам блока сравнения и управляющим входам корректора сигналов, первые - (И+1)-е выходы блока йамяти i-й ступени декодирования

50 соединены с одноименными входами корректора сигналов, первые - (N+1) -е выходы преобразователя скорости поступления символов подключены к одноименным информационным входам блока

55 памяти и входам декодера внутреннего записываются с частотой F по разрешающему сигналу А в блок 21, В это же время полученные векторы ошибок вместе с информационным бло"

5 ком, имеющим "1" на позициях стираний, и значениями прямой и обратной надежностей (полученными на первом и втором входах блока 17) поступают в блок 20 объединения сигналов, в котором коммутируются соответствующие надежности для определения цены декодирования слов.

Полученные на W-разрядных выходах блока 20 T +1 сигналов суммируются порознь с частотой F e блоке 22 сум1 мирования, а из результирующих Т +1 сигналов на его (W9 )-разрядных вы- ходах, поступающих в блок 23, определяется номер минимального из этих 0 сигналов, который управляет коммутацией исправленных сигналов блока 19 . декодирования, поступаюц|их на входы кода в первой ступени декодирования,. первые — (И+1) -е выходы корректора сигналов 1. и ступени декодирования соединены с одноименными информационными входами блока памяти и входами декодера внутреннего кода (i+1) -й ступени декодирования, j-e выходы блока памяти в j-й ступени декодирования соединены с вторыми входами блока сравнения этой ступени декоди" рования, выходы которого являются

j -ми выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения помехоустойчивости устройства и точности декодирования, в устройство введен синхронизатор, а декодер внешнего кода в j-й ступени декодирования выполнен на блоке очередности стираний, блоке анализа сгораний, блоке сравнения локаторов, переключателе, блоке памяти надежностей, блоке памяти операций, блоке декодирования, блоке объединения сигналов, блоке оперативной памяти, блоке суммирования, блоке выбора номера минимального числа, мультиплексоре и блоке памяти жестких символов, информационные входы которого являются первыми информационными входами декодера внешнего кода, вторые выходы декодера. внутреннего кода подключены в декодере внешнего кода к информа, ционным входам блока памяти надежностей, первым информационным входам блока очередности стираний и первым входам блока анализа стираний, выходы которого соединены с управляющими, входами блока очередности, стираний, выходы первой и второй групп выходов которого подключены соответственно к информационным входам блока срав" нения локаторов, переключателя блока а нали за стираний, выходы блока <.cpa внения локаторов, переключателя и блока жестких символов подключены соот ветственно к информационным входам блока памяти стирайий и входам стираний и ошибок блока декодирования, выходы которого соединены с информационными -входами блока оперативной памяти и входами ошибок блока объе" динения сигналов, первые и вторые вы" ходы блока памяти надежностей и выходы блока памяти стираний подключены соответственно к первым и вторым входам надежностей и входам стираний блока объединения сигналов, выходы которого соединены с соответствующими информационными входами блока сумми1543552 рования, выходы которого подключены к сост ветст вующим и нформа ционным входам блока выбора номера минимального числа, выходы которого и выходы блока оперативной памяти соединены соответственно с управляющими и информацион-, ными входами мультиплексора, выходы которого являются выходами декодера вн шнего кода, вход синхронизатора яв яется входом синхронизациИ устро ства, первый выход синхронизатора подключен к тактовому входу считывани преобразователя скорости поступлейия символов, тактовым входам блоков памяти всех ступеней декодирЬва" ни и тактовым входам записи блока паМяти жестких символов, блока памяти на ежностей, блока памяти стираний и лока оперативной памяти в декодере внешнего кода j -й ступеней декодирования, второй выход синхронизатора соединен в декодере внешнего кода (j-й ступени декодирования с входами

| управления записью блока очередности 25 стираний, блока памяти жестких символоб, блока памяти надежностей и блока оперативной памяти, третий выход синхрОнизатора подключен к входу управления записью блока памяти стираний у1 в Декодере внешнего кода j-й ступени декодирования, четвертые выходы синхр низатора соединены с вторыми инфо мационными входами блока очередно ти стираний и опорными входами блфка сравнения локаторов в декодере внешнего кода j-й ступени декодирования, пятый выход синхронизатора подклЮчен к тактовому входу записи преобразователя скорости поступления 4п символов, j-e выходы первой группы выходов синхронизатора соединены в декодере внешнего кода j -й ступени декодирования с управляющими входами переключателя и блока объедийения 4 сигналов, j-й выход второй группы

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

2, Устройство по g1, О т л и 4 а- 5 ю щ е е с я тем, что блок очередности стираний содержит первый - (2Т„ )-й коммутаторы (Т; и Гс1 /21; Г J - целая часть числа d - хэммингово рас1 стояwe j--го внешнего кода), первый (4Т ) -й буферные регистры и элемент

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

И подключен к тактовым входам всех буферных регистров, первые и вторые информационные входы всех коммутаторов соответственно объединены и являются одноименными входами блока, управляющие -входы всех коммутаторов являются управляющими входами блока, первые и вторые выходы m-ro коммутатора (m = 1,2Т) соединены с информационными входами соответственно (2m-1) -го и (2m) -го буферных регистров, выходы которых подключены соответственно к третьим и четвертым информационным входам ш-го и пятым и шестым информационным входам (в+1)-го коммутаторов и являются соответствующими выходами первой и второй групп выходов блока.

3. Устройство по и.1, о т л и ч аю щ е е с я тем, что блок объедине- . ния сигналов содержит группу источников постоянных кодов, группу элементов равнозначности, группу элементов

ИЛИ, первый и второй элементы ИЛИ и первый и второй элементы И, первые входы первого и прямые входы второго элементов И являются соответственно первыми и вторыми, входами надежностей блока, прямые и инверсные входы первого элемента ИЛИ являются входами соответственно ошибок и стираний блоI ка, выходы первого элемента ИЛИ под- ключены к вторым входам первого и инверсным входам второго элементов И, выходы которых соединены с первыми и вторыми входами второго элемента

ИЛИ, выходы которого подключены к первым входам всех элементов ИЛИ группы, выходы источников постоянного кода группы соединены с первыми входами одноименных элементов равнозначности группы, вторые входы которых соответственно объединены и являются управляющими входами блока, выходы элементов равнозначности группы подключены к вторым входам одноименных элементов ИЛИ группы, выходы которых являются соответствующими выходами блока.

4. Устройство по и.1, о т л и ч аю щ е е с я тем, что синхронизатор содержит генератор тактовых импульсов, первый и второй счетчики, умно13

1543 552 житель частоты, первый-третий дешифраторы, первый и второй триггеры . элемент ИЛИ-НЕ, группу счетчиков, группу умножителей частоты и блок выделения синхронизирующих меток, 5 вход которого является входом синхронизатора, а выход соединен с входом обнуления второго счетчика, выход генератора тактовых импульсов подклю-, чен к. входам йервого счетчика, умножителя частоты и умножителей частоты группы и является первым выходом синхронизатора, выход младшего разряда первого счетчика соединен с соответствующими входами всех дешифраторов, . выход старшего разряда первого счетчика подключен к входам счетчиков группы, Счетному входу второго счетчика и соответствующим входам всех 20 дешифраторов, выходы первого и тре" тьего дешифраторов соединены соответ) ственно c S-входом первого и R-входом второго триггеров, выход второго дешифратора подключен к R-входу первого и S-входу второго триггеров, прямой и инверсный вь ходы которых соединены соответственно с первым и вторым входами элемента ИЛИ-HE и являются вторым и третьим выходами синхрониза" тора, выходы второго счетчика подключены к соответствующим входам всех дешифраторов и являются четвертыми выходами синхронизатора, выход умно" жителя частоты является пятым выходом синхронизатора, выходы j-го счетчика группы вместе с выходом элемента ИЛИ-.

НЕ являются j-ми выходами первой группы выходов синхронизатора, выходы

j -го умножителя частоты группы являются 1-ми выходами второй группы выходов синхронизатора, 1543552 риар иии прись

° 4 ° епп8и

o) с, Ю иех метни

° ° °

СЛР

rz) ° ° °

Puz8

ГР17

a) ЯекодироВание у е е °

1543552

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

Техред M.Õîäàíè÷ Корректор И,пуска

Редактор А, nãàð

Заказ 4о8 Тираж 661 Подписное

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

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

Производственно-издательский комбинат Патент", r.Óæãoðoä, ул.Гагарина, 101