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

(51) М 13/ ОПИСАНИЕ ИЗОБРЕТЕНИ К АВТОРСКОМ ДЕТЕЛЬСТВУ ередачи и В.А,Зиновьев,робков, С.Н.Лиць 088.8 ктрон во СССР 7.о С ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР.(71) Институт проблем иформации АН СССР,(54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ БЛОЧНЫХ КОДОВ, СОГЛАСОВАННЫХ С МНОГО- ПОЗИЦИОННЫМИ СИГНАЛАМИ (57) Изобретение относится к вь.числительной технике и технике связи. Его использование в системах передачи информации позволяет повысить помехоустойчивость устройства и точность декодирования, Устройство для декодирования содержит преобразователь 1 скорости поступления символов и И ступеней 3 декодирования, каждая из которых включает блок 4 памяти, корректор 5 сигналов, декодер б внутреннего кода, декодер 7 внешнего кода и блок 8 сравнения. Благодаря специа фическому выполнению в каждой ступе1543552 Ъ Ь Составитель О.РевинскийРедактор А.Огар Техред М,Ходанич Коррект ус Заказ 408 Тираж 661 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб д, 4/5 зводственно-издательский комбинатПатент", г.ужгород, ул,Гагарина, 1013 13 У 4 15 20 25 30 35 40 45 50 55 ни Э декодирования декодера 7 внешнего кода, а также введению синхронизатора осуществляется последовательное декодирование вложенных кодов, .Изобретение относится к вычислиельной технике и технике связи и моет быть использовано в системах передачи информации.Цель изобретения - повышение помехоустойчивости декодирования устройства и точности.На фиг.1 представлена блок-схемаустройства, на фиг.2-7 - схемы соответственно блока очередности стираний, блока объединения сигналов, уза суммирования, блока выбора номераМинимального числа, компаратора исинхронизатора, на фиг.8 - временныериаграммы работы устройства, нафиг,9 - пространство сигналов внутрейнего кодирования,Устройство содержит (фиг.1) преобразователь 1 скоростей поступлениясимволов, синхронизатор 2 и Б ступеней 3 декодирования (И - число внеш,них кодов во входном сигнале), каждая из которых включает блок 4 па,мяти, корректор 5 сигналов, декодер6 внутреннего кода, декодер 7 внешнего кода и блок 8 сравнения. Нафиг.1 обозначены также информационныевходы 9, вход 10 синхронизации и выходы 11. В описании приняты следующие обозначения; 1, - разрядностьсимволов 1-го (3 = 1,М) внешнего кода (п, К;, Й 1), где и, К и с 1 - соответственно общее число символов,число информационных символов и хэммингово расстояние 3 -го кодаМ1.= М; Ы - чи сло бит надежности ,Х1 = 11 ор и Г, гдеГ - ближайшеебольшее целое,=1.ор (Т+ 1) ,Т ( ГЙ /2, где Г- целая частьлчисла,= ь + 1.Декодер 1 .1 внешнего кода в 3-йступени 3.1 декодирования содержит(фиг.1) блок 12 очередности стираний,блок 13 анализа стираний, блок 1 чсравнения локаторов, переключатель15, блок 16 памяти жестких символов,блок 17 памяти надежностей, блок 18памяти стираний, блок 19 декодировапричем каждое из декодированных словпредыдущего кода корректирует информацию, подлежащую дальнейшему декодированию. 3 э,п. Ф-лы, 9 ил. ния блок 20 объединения сигналов,блок 21 оперативной памяти, блок 22суммирования, блок 23 выбора номераминимального числа и мультиплексор 21,блок 12 очередности стираний образуют (фиг.2) коммутаторы .25, буферные регистры 26 и элемент И 27. Нафиг.2 обозначены также выходы 28.Блок 13 анализа стираний представляет собой набор элементов сравнения, каждый из которых имеет выходы "Больше или равно" и "Меньше,Блок 11 сравнения локаторов представляет собой группу элементов равнозначности, выходы которых соединеф ны с входами элемента ИЛИ, Первые входы элементов равнозначности образуют информационные входы блока,вторые их входы объединены и являют"ся управляющими входами блока.Блок 16 памяти жестких символов,а также блок 18 памяти стираний иблок 21 оперативной памяти выполненына оперативных запоминающих устройства (ОЗУ) .Блок 17 памяти надежностей выполнен на ОЗУ, выходы которого, являющиеся первыми выходами блока, подключены к входам преобразователя кодов, выполненного на программируемомпостоянном запоминающем устройстве(ППЗУ), выходы которого являются вторыми выходами блока. ПреобразовательФормирует из сигнала а сигнал Ь =( Ь; - а) где- минимальноеУевклидово значение системы сигналовна 1-м шаге декодирования,Блок 19 декодирования обеспечивает направление ошибок и стираний и выполнен аналогично известному,Блок 20 объединения сигналов содержит (фиг.3) первый и второй элементы ИЛИ 29, первый и второй элементы И 30, группу источников 31 постоянного кода, каждый иэ которых геерируег коды чисел 1 2,Т + 1 ф группу элементов 32 равнозначности и группу элементов ИЛИ 33.5 15435Блок 22 суммирования состоит изоднотипных на кали вающих сумматоров,каждый из которых содержит (фиг.4)сумматор 34 и буФерный регистр 35,Входы 000 001 010 011 100 101 110 111 Выходы 11 01 10 01 11 00 1 О 00 Предположим, цто к началу 1-го ша Б га Декодирования уже найдены векторы.М а Г 1, Далее внутреннимкодом Х декодируется каждый столбецматриц В В результате получаютсявектор а с Хи число Ь20 характеристика надежности, равнаяквадрату кодового расстояния от принятого слова до ближайшего в ансамбле Х 1, если оно меньше Ь, и равнаяв противном случае (зависимостьмежду надежностью и ее характеристикой обратная), Затем осуществляетсядекодирование вектора внешнего кодааГ = (аФ, , аф) эа Т + 1 по"1пыток, где Т ( Гд /2 , В Б-й попыт ке (Б = 1,Т +1) декодируется вектора Г со стертыми 2(Б) наименее. надежными символами, Пусть а) (Б)результат такого декЬдирования. Емуможно поставить в соответствие число Т (Б) = ;(Б, 1), где произвольГ)8-ный член суммы равен Ь "- Ц )если;1-й символ 1-го внешнего кода ошибочен и не стерт, и равен ( Ь - Ь (в противном случае.В качестве декодированного слова1-го кода выбирается а( (Б) с минимальным ТГ"(Б). Для 1-го шага декодирования это слово является выходными используется для коррекции матрицы(как в известном устройстве), послечего осуществляется переход к (1+1)му шагу,Теория- показывает, что если нахо-диться в пределах корректирующей способности СКК (расстояние от векторашума до переданного вектора меньшеР /4), то принятое слово всегда де"кодируется верно,Устройство для декодирования блоч-ных кодов, согласованных с многопозиционными сигналами, работает следующим образом. 35 40 45 50 55 Блок 23 выбора номера минимального числа аналогично известному и содержит (фиг.5) компараторы 36, соеСинхронизатор 2 содержит (фиг.7) генератор 40 тактовых импульсов, первый и второй счетчики 4 1 и 42 с модулями соответственно М и и, блок 43 выделения синхрониэирующих меток, умножитель 44 частоты на 1 , первый - третий дешифраторы 45 чисел соответственно 0, и+1 и 2 п+1, первый и второй триггеры 46, элемент ИЛИ-НЕ 47 группу счетчиков 48 с модулями Т+ 1 и группу умножителей 49 частоты на Т + 1. На фиг.7 обозначены первый-третий, четвертые и пятый выходы 50-54, а также первая и вторая группы 55 и 56 выходов.Преобразователь 1 скорости поступления символов выполнен на ОЗУ. Блок 4, памяти также выполнен на ОЗУ.Корректор 5. сигналов может быть реализован на ППЗУ или сумматоре. Декодер 6. внутреннего кода представляет собой ППЗУ, реализующее алгоритм декодирования по максимуму правдоподобия в ансамбле сигналов Х1Устройство для кодирования, сопряженное рассматриваемому устройству для декодирования, а также канал связи идентичны известным. При этом на выходах канала связи (входах устройства для декодирования) формируются символы жесткого решения (М старших разрядов) и надежности (И младших разрядов).Рассматриваемое устройство реалиФзует следующий алгоритм декодирования, являющийся обобщением алгоритма известного устройства. лпусть В Й Р32 В = 1 Яье 1, 1 э о э 1 ф 1 = 1 э(1+ э1,п, - матрицы переданного и принятого (подлежащего декодированию) слова выбранной сигнально-кодовой конструкции (СКК), Декодирование про" водится за Е шагов (ступеней), на каждом из которых находится словоа(1)А; внешнего кода А 1.,526диненные по пирамидальной схеме, и вычислитель 37 возможной ошибки, Компаратор 36, как в известном устройстве выполнен (фиг,6) на элементе 38 сравнения и элементе 2 И-ИЛИ 39. Выцислитель 37 возможной ошибки выполнен на ППЗУ, которое реализует следующий алгоритм (для Т = 3):На входы 8 устройства поступает последовательность иэа сигналов, каждому из которых соответствует М бит жесткого решения (жестких бит) и И бит надежности. Эти сигналы за,писываются в преобразователь 1 скорости - ОЗУ емкостью (И+И),й - с частотой 1 Р, с которой ойи поступают из канала связи, а считываются 1 О с частотой Г в виде кодовых слов внутреннего кода СКК. В результате на выходе преобразователя 1 образуется матрица= ( 1, жестких сигналов с ошибками и их надежностей, 15 причем для каждого элементапри фиксированном 1 первые 1 И сигналов соответствуют жесткому значению сигнала, а остальные О И сигналов отвечают надежности, Эта матрица в 20 первой ступени 3.1 декодирования запоминается в блоке 4.1 памяти емкостью(М + И) х Зп на время 3 а тактов частоты Р - время декодирования слова первого внешнего кода, Одновременно каждый столбец матрицы В поступает в декодер 6 .1 внутреннего ко" да, в котором определяются номер подкода (поступающий на первый Ь -раз,рядный выход) и надежность (поступаю щая на второй У-разрядный выход), Работа этого блока иллюстрируется на фиг.9.Затем каждый из этих сигналов, составляющих сло иэ и свлов, пос- Э 5 ,тупает в декодер 7.1 внешнего кода, на выходах которого в результате об,работки формируется первый вектор ошибки, который в блоке 8.1 сравнения сопоставляется с задержанной первой 40 строкой входной матрицы Р. Результатом этого сопоставления является информационное слово первого внешнего кода на выходах 11.1, Одновременно тот же вектор ошибки используется в 45 корректоре 5.1 сигнала для исправлеА ,ния первой строки матрицы В.Далее такой процесс последовательно повторяется в дальнейших ступенях 3 декодирования. В конечном счете на выходах 1 образуется Б информационных слов, близость которых к исходным словам (на передаче) определяется эффективностью предлагаемого обобщенного алгоритма декодирования.Рассмотрим обработку сигналов в произвольном декодере 7 3Символы надежностей поступившие на входы декодера 7.1, подаются в блок 12 очередности стираний, внутрикоторого в четных регистрах 26 хранятся значения 2 Т наименьших надежностей в информационном блоке иэ псимволов и их адреса в этом блоке впорядке возрастания надежностей, С.приходом каждого нового сигнала сначала он ставится на полагающуюся емупозицию, так что к концу информационного блока в блоке 12 образуются ввозрастающем порядке 2 Т самых нена-,.дежных сигналов и их адресаПолученные в блоке 12 текущие 2 Т 1значения надежностей с его вторыхвыходов 28.2 подаются в блок 13 анализа стираний, где с ними сравниваютсянадежности каждого сигнала, поступающего на входы блошка 13. На его вы"ходах вырабатывается управляющийсигнал, указывающий, нужно ли вставлять данный текущий сигнал куда-либов середину списка из 2 Т самых нес,1надежных сигналов, или же его. надежность выше всех этих 2 т надежностей9записанных в четных регистрах 26блока 12.Сформированные в блоке 12 адресанадежностей (называемые далее локаторами) с его первых выходов 28.1поступают одновременно в блок 14сравнения локаторов и на переключатель 15,В блок 15 поступает также на егоуправляющие входы сигнал Р с выходов53 синхронизатора 2. За и тактов внем формируется информационный блок,имеющий "0" на позициях где стиранийнет, и "1" в позициях со стираниями,Этот информационный блок поступаетв блок 18 ОЗУ, где записывается счастотой Р, а,считывается с парциальной частотой Р.В то же время переключатель 15 поочереди (по командам парциальногоуправляющего сигнала С) пропускаетлокаторы 0, 2, 4, , 2 Т в соответствии с (Т +1) -й попыткой декодирования.Поступающие на Ь -разрядные входы3декодера 7. жесткие символы записываются в блок 16 по разрешению сигнала А с частотой Р, а считываютсяс частотой Г;.Считанные жесткие символы одновременно с локаторами поступают в блок19 декодирования, в котором исправляются ошибки и стирания. Результатыдекодирования в виде векторов ошибкимультиплексора 2 ч на выходы которогопропускается соответствующий вектор 25ошибки,формула изобретения 1. Устр ойст во для де кодир ова ни яблочных кодов, согласованных с много позиционными сигналами, содержащеепреобразователь скорости поступлениясимволов, информационные входы которого являются информационными входами устройства, и первую - И-ю ступени декодирования (И - число внешних кодов во входном сигнале), -я ступень декодирования (1 = 1 И) содержит 35 блок памяти, декодер внутреннего кода, декодер внешнего кода блок срав нения и корректор сигналов, И-я ступень декодирования содержит блок памяти, декодер внутреннего кода, деко" дер внешнего кода и блок сравнения,первые выходы декодера внутреннегокода 1-й ступени декодирования(,1 = 1 Н) соединены с первыми информа ционными входами декодера внеш" 45 него кода, выходы которого подключены к первым входам блока сравнения иуправляющим входам корректора сигналов, первые - (И+1)-е выходы блокайамяти -й ступени декодирования 50 соединены с одноименными входами корректора сигналов, первые - (И+1) - .евыходы преобразователя скорости поступления символов подключены к одноименным информационным входам блока 55 памяти и входам декодера внутреннего записываются с частотой Р по разрешающему сигналу А в блок 21,В это же время полуЧенные векторы ошибок вместе с информационным бло"5 ком, имеющим "1" на позициях стираний, и значениями прямой и обратной надежностей (полученными на первом и втором входах блока 17) поступают в блок 20 объединения сигналов, в котором коммутируются соответствующие надежности для определения цены декодирования слов.Полученные на Н-разрядных выходах блока 20 Т+1 сигналов суммируются порознь с частотой Г в блоке 22 суммирования, а из результирующих Т +1 сигналов на его (У )-разрядных вы- ходах, поступаюцих в блок 23, определяется номер минимального из этих сигналов, который управляет коммутацией исправленных сигналов блока 19 . декодирования поступаюцих на входы кода в первой ступени декодирования,.пер вые - (И+1) -е выходы корр ек торасигналов х-й ступени декодирования соединены с одноименными информационными входами блока памяти и входами декодера внутреннего кода (1+1)-й ступени декодирования, 1-е выходы блока памяти в 1-й ступени декодирования соединены с вторыми входами блока сравнения этой ступени декоди" рования, выходы которого являются 1-ми выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения помехоустойчивости устройства и точности декодирования, в устройство введен синхронизатор, а декодер внешнего кода в 1-й ступени декодирования выполнен на блоке очередности стираний, блоке анализа сгораний блоке сравнения локаторов, переключателе, блоке памяти надежностей, блоке памяти операций, блокедекодирования, блоке объединения сигналов, блоке оперативной памяти, блоке сумми рова ни я, блоке выбора номера минимального числа, мультиплексоре и блоке памяти жестких символов, информационные входы которого являются первыми информационными входами декодера внешнего кода, вторые выходы декодера внутреннего кода подключены в декодере внешнего кода к информа ционным входам блока памяти надежностей первым информационным входамблока очередности стираний и первымвходам блока анализа стираний, выходыкоторого соединены с управляющими,входами блока очередности, стираний,выходы первой и второй групп выходовкоторого подключены соответственнок информационным входам блока срав"нения локаторов, переключателя блокаанализа стираний, выходы блока:сравнения локаторов, переключателя и блока жестких символов подключены соот ветственно к информационным входам блока памяти стирайий и входам стираний и ошибок блока декодирования, выходы которого соединены с информационными .входами блока оперативной памяти и входами ошибок блока объе"динения сигналов, первые и вторые вы" ходы блока памяти надежностей и выходы блока памяти стираний подключены соответственно к первым и вторым входам надежностей и входам стираний блока объединения сигналов, выходыкоторого соединены с соответствующими информационными входами блока сумми 1543552рования, выходы которого подключены к сост ветст вующим и нформа ционным входам блока выбора номера минимального числа, выходы которого и выходы блока оперативной памяти соединены соответственно с управляющими и информацион-, ными входами мультиплексора, выходы которого являются выходами декодера вн шнего кода, вход синхронизатора яв яется входом синхронизациИ устро ства, первый выход синхронизатора подключен к тактовому входу считывани преобразователя скорости поступления символов, тактовым входам блоков памяти всех ступеней декодирЬва" ни и тактовым входам записи блока памяти жестких символов, блока памяти на ежностей, блока памяти стираний и лока оперативной памяти в декодере внешнего кода 1-й ступеней декодирования второй выход синхронизатора соединен в декодере внешнего кода 1-й ступени декодирования с входами упавления записью блока очередности 25 стираний блока памяти жестких символов блока памяти надежностей и блока оперативной памяти, третий выход синхронизатора подключен к входу управления записью блока памяти стираний ЗО в Декодере внешнего кода 1-й ступени декодирования четвертые выходы синхр низатора соединены с вторыми инфо мационными входами блока очеред- но ти стираний и опорными входами блфка сравнения локаторов в декодере внЕшнего кода 1-й ступени декодирова- ниМ, пятый выход синхронизатора подклЮчен к тактовому входу записи преобразователя скорости поступления 4 О символов 1-е выходы первой группы выходов синхронизатора соединены в декодере внешнего кода -й ступени декодирования с управляющими входами переключателя и блока объединения 45 сигналов, 1-й выход второй группы выходов синхронизатора подключен в декодере внешнего кода 1-й ступени декодирования к тактовым входам блока очередности стираний и блока сумми" рования и тактовым входам считывания блока памяти жестких символов, блока памяти надежностей блока памяти стираний и блока оперативной памяти.2, УстРойство по О.1, о т л и ч а ю щ е е с я тем, что блок очередности стираний содержит первый - (2 Т)-й коммутаторы (Т; с Гс 1/2; Г- целая часть числа д - хэммингово рас 3 стояние 1-го внешнего кода), первый (1 Т)-й буферные регистры и элемент И, йервый и второй входы которого являются входом управления записью и тактовым входом блока, выход элемента И подключен к тактовым входам всех буферных регистров, первые и вторые информационные входы всех коммутаторов соответственно объединены и являются одноименными входами блока, управляющие входы всех коммутаторов являются управляющими входами блока, первые и вторые выходы ш-го коммутатора (ш = 1,2 Т) соединены с информационными входами соответственно ф = (2 ш) -го и (2 ш) -го буферных регистров, выходы которых подключены соответственно к третьим и четвертым информационным входам ш-го и пятым и шестым информационным входам (а+1)-го коммутаторов и являются соответствующими выходами первой и второй групп выходов блока.3. Устройство по и.1, о т л и ч аю щ е е с я тем, что блок объедине- . ния сигналов содержит группу источников постоянных кодов, группу элементов равнозначности, группу элементов ИЛИ, первый и второй элементы ИЛИ и первый и второй элементы И, первые входы первого и прямые входы второго элементов И являются соответственно первыми и вторыми, входами надежностей блока, прямые и инверсные входы первого элемента ИЛИ являются входами соответственно ошибок и стираний блока, выходы первого элемента ИЛИ под- ключены к вторым входам первого и инверсным входам второго элементов И, выходы которых соединены с первыми и вторыми входами второго элемента ИЛИ, выходы которого подключены к первым входам всех элементов ИЛИ группы выходы источников постоянного кода группы соединены с первыми входами одноименных элементов равнозначности группы, вторые входы которых соответственно объединены и являются управляющими входами блока, выходы элементов равнозначности группы подключены к вторым входам одноименных элементов ИЛИ группы, выходы которых являются соответствующими выходами блока.Устройство по и.1, о т л и ч аю щ е е с я тем, что синхронизатор содержит генератор тактовых импульсов, первый и второй счетчики, умно 1543552 14житель частоты, первый-третий дешифраторы, первый и второй триггеры.элемент ИЛИ-НЕ, группу счетчиков, группу умножителей частотыи блок выделения синхронизирующих меток,5 вход которого является входом синхро. низатора, а выход соединен с входом обнуления второго счетчика, выход генератора тактовых импульсов подклю-, чен к. входам йервого счетчика, умно- жителя частоты и умножителей частоты группы и является первым выходом синхронизатора, выход младшего разряда первого счетчика соединен с соответствующими входами всех девифраторов, выход старшего разряда первого счетчика подключен к входам счетчиков группц, Счетному входу второго счетчика и соответствующим входам всех 20 дешифраторов, выходы первого и тре" тьего дешифраторов соединены соответственно с Б-входом первого и К-входоювторого триггеров, выход второго дешифратора подключен к К-входу первого и Б-входу второго триггеров, прямой и инверсный вьходы которых соеди"нены соответственно с первым и вторымвходами элемента ИЛИ-НЕ и являютсявторым и третьим выходами синхрониза"тора, выходы второго счетчика подключены к соответствующим входам всехдешифраторов и являются четвертымивыходами синхронизатора, выход умно"жителя частоты является пятым выходомсинхронизатора, выходы "го счетчикагруппы вместе с выходом элемента ИЛИ".НЕ являются 1-ми вцходами первойгруппы выходов синхронизатора, выходы1-го умножителя частоты группы являются 1-ми выходами второй группы выходов синхронизатора,