Устройство для декодирования блочных кодов, согласованных с многопозиционными сигналами Советский патент 1990 года по МПК H03M13/05 

1

(21)4370501/2k-2k

(22)07.12.8

(46) 15.02.90. Бюл. V 6

(71)Институт проблем передачи информации АН СССР

(72)А.С,Данилин, В.А.Зиновьев, В.В.Зяблов, Д.Л.Коробков, С.Н.Лицын и С.Л.Портной

(53) 681.325:621.394.14(088.8) (56) Зарубежная радиоэлектроника, 1985, п.7, с. 3-26.

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

Авторское свидетельство СССР по заявке № 4158884/24, кл. Н 03 М 13/00, 1986.

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

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

Bj

сп

Јь 00 СП СП IsD

is

19

фиг-i

f

/;

Ни Э декодирования декодера 7 внешнего кода, а также введению синхронизатора осуществляется последовательное декодирование вложенных кодов,

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

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

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

Устройство содержит (фиг.1) преобразователь 1 скоростей поступления символов, синхронизатор 2 и N ступеней 3 декодирования (N - число внешних кодов во входном сигнале), каждая из которых включает блок А памяти, корректор 5 сигналов, декодер 6 внутреннего кода, декодер 7 внешнего кода и блок 8 сравнения. На фиг.1 обозначены также информационны входы 9 вход 10 синхронизации и вы- хрды 11. В описании приняты следующие обозначения: I/. разрядность символов j-го (j 1,N) внешнего ко- +даДп, Kj, dj), где n, Kj и dj - соответственно общее число символов, число информационных символов и хэм- мингово расстояние j-ro кода;

N L, M; W - число бит надежности

NO 11ор,гп Г - ближайшее большее целое, Ј lopl5,(T j + 1) Г, Т; -fd , где - целая часть

I Л л

числа, с с. + 1 .

Декодер | . j внешнего кода в j-й ступени 3.J декодирования содержит (фиг.1) блок 12 очередности стираний блок 13 анализа стир-аний, блок сравнения локаторов, переключатель 15, блок 16 памяти жестких символов, блок 17 памяти надежностей, блок 18 памяти стираний, блок 19 декодировапричем каждое из декодированных слов предыдущего кода корректирует информацию, подлежащую дальнейшему декодированию. 3 з.п, ф-лы, 9 ил.

ния, блок 20 объединения сигналов, блок 21 оперативной памяти, блок 22 суммирования, блок 23 выбора номера минимального числа и мультиплексор 2k.

5 блок 12 очередности стираний образуют (фиг.2) коммутаторы 25, буферные регистры 26 и элемент И 27. На фиг.2 обозначены также выходы 28. Блок 13 анализа стираний пред0 ставляет собой набор элементов сравнения, каждый из которых имеет выходы Больше или равно и Меньше.

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

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

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

5 (А, - а)2, где & - минимальное евклидово значение системы сигналов на j-м шаге декодирования.

Слок 19 декодирования обеспечивает 0 направление ошибок и стираний и выполнен аналогично известному.

Блок 20 объединения сигналов содержит (фиг.З) первый и второй элементы ИЛИ 29, первый и второй элементы И 30, группу источников 31 пос5

5

тоянного кода, каждый из которых генерирует коды чисел 1, ., ..., TJ + 1, группу элементов 32 равнозначности и группу элементов ИЛИ 3.

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

Блок 23 выбора номера минимального числа аналогично известному и соСинхронизатор 2 содержит (фиг.7) генератор 40 тактовых импульсов, первый и второй счетчики 41 и 42 с модулями соответственно N и п, блок 43 выделения синхронизирующих меток, умножитель 44 частоты на 06 , первый - третий дешифраторы 45 чисел соответственно 0, п+1 и 2п+1, первый и второй триггеры 46, элемент ИЛИ-НЕ 47, группу счетчиков 48 с модулями Tj + 1 и группу умножителей 49 частоты на Tj -f 1 . На фиг.7 обозначены первый-третий, четвертые и пятый выходы , а также первая и вторая группы 55 и 56 выходов.

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

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

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

Пусть В || р„рЦ, В П fih.gll ,

Ъ 1 о м h 1 M+W) 1 - 1,n, - матрицы переданного и принятого (подлежащего декодированию) слова выбранной сигнально-кодовой конструкции (СКК). Декодирование проводится за N шагов (ступеней), на каждом из которых находится слово a J 6 А внешнего кода А:.

15435526

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

Предположим, что к началу j-ro шага Декодирования уже найдены векторы

а , ..., . Далее внутренним кодом X; декодируется каждый столбец - матриц §.,В результате получаются вектор a J 6 X. и число A2p(j) характеристика надежности, равная квадрату кодового расстояния от принятого слова до ближайшего в ансамбле X j, если оно меньше U2, и равная А2 в противном случае (зависимость

между надежностью и ее характеристикой обратная), Затем осуществляется декодирование вектора внешнего кода ам (а( ..., за Tj + 1 попыток, где Tj rdj/2. В S-й попытке (s 1,T +1) декодируется вектор со стертыми 2(8-1) наименее, надежными символами. Пусть а (S) - результат такого декодирования. Ему можно поставить в соответствие число

/

TU) (S) 2L t (S,l), где произвольe-i

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

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

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

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

На входы 8 устройства поступает последовательность из }„ п сигналов, каждому из которых соответствует М бит жесткого решения (жестких бит) и W бит надежности. Эти сигналы записываются в преобразователь 1 скорости - ОЗУ емкостью ( - с частотой -50 F, с которой они поступают из канала связи, а считываются с частотой F в виде кодовых слов внутреннего кода СКК. В результате на выходе преобразователя 1 образуется матрица В Н fby, жестких сигналов с ошибками и их надежностей, причем для каждого элемента ft при фиксированном 1 первые М сигналов соответствуют жесткому значению CHI- нала, а осталоные 0 W сигналов отвечают надежности. Эта матрица в первой ступени 3.1 декодирования запоминается в блоке 4.1 памяти емкостью )0 (М + W) х Зп на время Зп тактов частоты F - время декодирования слова первого внешнего кода. Одновременно каждый столбец матрицы В поступает в декодер 6.1 внутреннего кода, в котором определяются номер под10

15

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

Полученные в блоке 12 текущие значения надежностей с его вторы выходов 28.2 подаются в блок 13 а

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

Сформированные в блоке 12 адре надежностей (называемые далее лок

25

кода (поступающий на первый LJ-разрядный выход) и надежность (поступаю- 30 торами) с его первых выходов 28.1 щая на второй W-разрядный выход). Ра- поступают одновременно в блок 14 бота этого блока иллюстрируется на фиг.9.

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

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

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

Символы надежностей, поступившие на входы декодера 7.J, подаются в

сравнения локаторов и на переключ тель 15.

В блок 15 поступает также на е

35 управляющие входы сигнал D с выхо 53 синхронизатора 2. За п тактов нем формируется информационный бл имеющий О на позициях, где стир нет, и 1 в позициях со стирания

40 Этот информационный блок посту в блок 18 ОЗУ, где записывается с частотой F, а считывается с парци ной частотой F:.

В то же время переключатель 15

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

50

55

Поступающие на L:-разрядные вх декодера 7.J жесткие символы запи ваются1 в блок 16 по разрешению CH нала А с частотой F, а считываютс с частотой FJ.

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

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

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

Сформированные в блоке 12 адреса надежностей (называемые далее лока

торами) с его первых выходов 28.1 поступают одновременно в блок 14

торами) с его первых выходов 28.1 поступают одновременно в блок 14

сравнения локаторов и на переключатель 15.

В блок 15 поступает также на его

управляющие входы сигнал D с выходов 53 синхронизатора 2. За п тактов в нем формируется информационный блок, имеющий О на позициях, где стираний нет, и 1 в позициях со стираниями.

Этот информационный блок поступает в блок 18 ОЗУ, где записывается с частотой F, а считывается с парциальной частотой F:.

В то же время переключатель 15 по

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

Поступающие на L:-разрядные входы декодера 7.J жесткие символы записываются1 в блок 16 по разрешению CHI- нала А с частотой F, а считываются с частотой FJ.

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

записываются с частотой Fj по разрешающему сигналу А в блок 21.

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

Полученные на W-разрядных выходах блока 20 Т: + 1 сигналов суммируются порознь с частотой Fj в блоке 22 суммирования, а из результирующих Tj+ b сигналов на его ()-разрядных выходах, поступающих в блок 23, определяется номер минимального из этих сигналов, который управляет коммута- цией исправленных.сигналов блока 19 декодирования, поступающих на входы мультиплексора 21, на выходы которог пропускается соответствующий вектор ошибки.

Формула изобр

е т е н и я

10

J5

20

25

30 4045CQ 552Ю

кода в первой ступени декодирования,., первые - (N+l)-e выходы корректора сигналов i-й ступени декодирования соединены с одноименными информационными вводами блока памяти и входами декодера внутреннего кода (i+1)-и ступени декодирования, j-e выходы блока памяти в j-й ступени декодирования соединены с вторыми входами блока сравнения этой ступени декодиа рования, выходы которого являются j-ми выходами устройства, отличающееся тем, что, с целью повышения помехоустойчивости устройства и точности декодирования, в устройство введен синхронизатор, а декодер внешнего кода в j-й ступени декодирования выполнен на блоке очередности стираний, блоке анализа сгораний, блоке сравнения локаторов, переключателе, блоке памяти надежностей, блоке памяти операций, блоке декодирования, блоке объединения сигналов, блоке оперативной памяти, блоке суммирования, блоке выбора номера минимального числа, мультиплексоре и блоке памяти жестких символов, информационные входы которого являются первыми информационными входами декодера внешнего кода, вторые выходы декодера внутреннего кода подключены в декодере внешнего .кода к информаг ционным входам блока памяти надежностей, первым информационным входам 35 блока очередности стираний и первым входам блока анализа стираний, выходы которого соединены с управляющими входами блока очередности стираний, выходы первой и второй групп выходов которого подключены соответственно к информационным входам блока сравнения локаторов, переключателя блока анализа стираний, выходы блока сравнения локаторов, переключателя и блока жестких символов подключены COOTW ветственно к информационным входам блока памяти стираний и входам стираний и ошибок блока декодирования, выходы которого соединены с информационными -входами блока оперативной памяти и входами ошибок блока объединения сигналов, первые и вторые выходы блока памяти надежностей и выходы блока памяти стираний подключены соответственно к первым и вторым входам надежностей и входам стираний блока объединения сигналов, выходы которого соединены с соответствующими информационными входами блока сумми55

11

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

№55212

стояние j-ro внешнего кода), первый (4Т|)-й буферные регистры и элемент И, первый и второй входы которого являются входом управления записью и тактовым входом блока, выход элемента И подключен к тактовым входам всех буферных регистров, первые и вторые информационные входы всех коммутаторов соответственно объединены и являются одноименными входами блока, управляющие входы всех коммутаторов являются управляющими входами блока, первые и вторые выходы m-го коммута- jc тора (т 1,2Т) соединены с информационными входами соответственно -- (2т-1)-го и (2т)-го буферных регистров, выходы которых подключены соответственно к третьим и четвертым ин10

и б;лока оперативной памяти в декоде- 2о Ф°РмаЧионным входам m-го и пятым и ре внешнего кода j-й ступеней деко-шестым информационным входам (пн-1)-го

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

25

35

40

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

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

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

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

i

житель частоты, первый-третий дешифраторы, первый и второй триггеры - элемент ИЛИ-НЕ, группу счетчиков, группу умножителей частоты и блок выделения синхронизирующих меток, вход которого является входом синхронизатора, а выход соединен с входом обнуления второго счетчика, выход генератора тактовых импульсов подключен к входам первого счетчика, умножителя частоты и умножителей частоты группы и является первым выходом синхронизатора, выход младшего разряда первого счетчика соединен с соответствующими входами всех дешифраторов, выход старшего разряда первого счетчика подключен к входам счетчиков группы, счетному входу второго счетчика и соответствующим входам всех дешифраторов, выходы первого и третьего дешифраторов соединены соответ- i

ственно с S-входом первого и R-входом второго триггеров, выход второго де- шифратора подключен к R-входу перво- , го и S-входу второго триггеров, прямой и инверсный выходы которых соединены соответственно с первым и вторым входами элемента ИЛИ-НЕ и являются вторым и третьим выходами синхронизаQ тора, выходы второго счетчика подключены к соответствующим входам всех ; дешифраторов и являются четвертыми выходами синхронизатора, выход умножителя частоты является пятым выходом

5 синхронизатора, выходы j-ro счетчика группы вместе с выходом элемента ИЛИ- НЕ являются j-ми выходами первой группы выходов синхронизатора, выходы j-ro умножителя частоты группы явля0 ются j-ми выходами второй группы выходов синхронизатора.

I. а.г

фигЛ

(риг.5

фиг 5

Ј

j.

7л

//

1

е

1

о

фиг. 3

W

7Z

1