Устройство для декодирования кода нордстрома-робинсона в дискретном канале

(Ю (И) А 1 Г 5)5 Н 03 М 13/00 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЭОБРЕТЕНИЯМ И ОТНРЫ 7 ИЯМОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Кодирование и передача дискретных сообщений по каналам связи,-М,:Наука, 1976, с. 74-75,Авторское свидетельство СССРР 1108618, кл, Н 03 М 13 У 02, 1980,(54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ КОДА НОРДСТРОМА - РОБИНСОНА В ДИСКРЕТ"НОМ КАНАЛЕ 2 (57) Изобретение относится к вычислительной технике и может быть исполь-,/ зовано при разработке аппаратуры передачи Дискретной информации, Цель изобретения - повышение корректирующей способности и быстродействия устройства за счет сложения входного кодового слова с образующими смежных классов и декодирования полученных кодовых слов усеченными декодерами кода Рида" Маллера, Устройство содержит 7 блоков сложения с образующими смежного класса (1), 8 усеченных декодеров кода Рида-Маллера (2) блок ключей (3), блок сравнения (4) и выходной буферный регистр (5), 1-2-4"3"5, 2"3; 4-5 1 ч и ф-лы 3 ил,3 173Изобретение относится к информатике и вычислительной технике, конкретно к устройствам декодирования кодаОордстрома-Робинсона, и может бытьиспользовано при разработке аппаратуры передачи дискретной информации,Известно устройство декодированиякода Нордстромв-Робинсона, основанноена разбиении кода на биортогональныеподкоды с помощью преобразования Уолша, Данное устройство предназначенодля декодирования широкого класса кодов, разбивающихся на биортогональные,и для кода Нордстрома-Робинсона неявляется оптимальным,Устройство содержит восемь блоковдекодирования биортогонального кода,основанных на быстром преобразованииУолша и схемы выбора максимальногоэлемента,Наиболее близким техническим решением является устройство декодированиякода Нордстрома-Робинсона, содержащееблок сравнения, выходы которого соединены с управляющими входами блокаключей, а также преобразователь приня"того слова, дешифратор, обнаружитель1 шибок, четырех- и пятиразрядный счетчики, два блока управления, тактовыйгенератор, два пороговых элемента,кодер кода Рида-Соломона, кодер кодаНордстрома-Робинсона.Недостатками известного устройстваявляется низкое быстродействие и боее низкая по сравнению с максимумомправдоподобия корректирующая способность,Цель изобретения - повышение быстродействия и достижение корректирующейспособности по максимуму правдоподобия.Поставленная цель достигается тем,что в устройство, содержащее блоксравнения, выходы которого соединеныс управляющими входами блока. ключей,введены первый-восьмой усеченные декодеры кода Рида-Маллера выходнойбуферный регистр и первый-седьмойблоки сложения с образующими смежногокласса, входы которых и входы первогоусеченного декодера кода Рида-Маллерасоответственно объединены и являютсявходами устройства, выходы первогоседьмого блоков сложения с образующими смежного класса подключены к входам соответственно второго - восьмогоусеченных декодеров кода Рида-йаллера,первые - пятые выходы всех усеченныхдекодеров кода Рида-Маллера соединены 6008с соответствующими информационнымивходами блока ключей, выходы которогосоединены.с первыми входами выходногобуферного регистра, вторые входы ко"торого подключены к выходам блокасравнения, шестые выходы всех усечен"ных декодеров кода Рида-Маллера сое-"динены с входами блока сравнениявы- О ходы выходного буферного регистра яв-ляются выходами устройства.Кроме того, в устройстве усеченныйдекодер кода Рида-Маллера содержитблоки сложения-вычитания, блоки суммирования модулей, блоки сравнения,блоки ключей и блок определения знакачисла, входы первого блока сложениявычитания являются входами декодера,первые выходы первого .- третьего бло О ков сложения-вычитания соединены спервыми информационными входами одноименных блоков ключей и входами адно"именных блоков суммирования модулей,выход каждого блока суммирования мо" 25 дулей подключен к входу одноименногоблока сравнения, вторые выходы перво"го - третьего блока сложения-вычитания соединены с .вторыми информацион.- ными входами одноименных блоков ключей, выходы которых подключены к входам соответственно второго-четвертогоблоков сложения вычитания, первый выход четвертого блока сложения-вычита-,ния соединен с входом четвертого. бло- .ка сравнения и первым информационным 35 входом четвертого блока ключей, второй выход четвертого блока сложениявычитания подключен к второму информационному входу четвертого блока ключей, прямые выходы первого-четвертого о блоков сравнения соединены с первымиуправляющими входами одноименных блоков ключей и являются соответственнопервым-четвертым выходами декодера,инверсные выходы первого-четвертого 45 блоков сравнения подключены к вторымуправляющим входам одноименных блоковключей, выход блока определения знакачисла является пятым выходом декодера,выход четвертого блока ключей соеди 5 О нен с входом блока определения знака числа и является шестым выходом блока,На фиг.изображена структурнаясхема устройства для декодирования55 кода Нордстрома-Робинсона. на фиг,2усеченный декодер кода Рида-Маллера;на фиг. 3 " граФ-схема,Устройство для декодирования кодаНордстрама-Робинсона содержит блоки 1делах кодового расстояния (6=8), т,е,исправляющее ошибки кратности тривключительно, Декодер кодов Нордстрома-Робинсона будет тогда исправлятьвсе двухкратные ошибки; а также тетрехкратные и четырехкратные ошибки,которые исправляются при декодировании по максимуму правдоподобия, Поскольку результаты работы декодирующегоустройства, работающего по максимумуправдоподобия, и устройства усеченного декодирования (декодирование в пределах кодового расстояния) для векторов с ошибками кратности 0,1,2,3 однии те же и поскольку вектора с пятью,шестью кратными ошибками будут в каком-то смежном классе являться векторами с ошибками кратности, меньшейпяти, и так как в столбце таблицыстандартного расположения должно находиться ровно определенное число векторов, то число правильно декодируемых векторов с ошибками кратности четыре при работе декодера кода РидаМаллера по максимуму правдоподобия иработе усеченного декодера будет одинаковым, Следовательно, устройстводля декодирования кода Нордстрома-Робинсона, использующее усеченный декодер кода Рида-Маллера, будет устройством декодирования по .максимуму прав.доподобия (данное утверждение проверено на ЭВ)1 путем декодирования двумяспособами всех двоичных последовательностей длины 16).П р и м е р, Пусть в линию связипослан вектор длины 16 ч = (1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1),На приемной стороне принимаетсявектор ч = (-1, 1, 1, 1, 1, -1, 1, 1,1, -1, 1, 1, 1, 1, 1, 1) с ошибкамина первой, шестой и десятой позициях.Элементы принятого вектора попарноскладываем и вычитаем, затем находимсумму з модуЛей элементов, полученныхсложением, и сравниваем ее с восемью,Если в8, то на дальнейшее декодирование пропускаем элементы, полученные сложением, если з0, то на дальнейшее декодирование пропусканием элементы, полученные вычитанием, при этомна каждом шаге получаем очередной информационный символ (1 если з3, 1если з СЯ), На последнем шаге определяем знак элемента (полученного сложением, если в ъ 8), полученного вычитанием, если в(8) " это дает пятый ин 45 5 1736008 6сложения с образующим смежного клас-са, усеченные декодеры 2 кода Рида Маллера, блок 3 ключей, блок 4 сравнения, . выходной буферный регистр 5.Блок 1 сложения с образующим смежного класса представляет собой наборшести инверторов, инвертирующих элементы исходного вектора в соответствиис образующим данного смежного классаБлок 3 ключей представляет собойнабор ключей, которые на выход бло-,ка пропускают пять информационных символов с усеченного декодера кодаРида"Маллера, имеющего максимальнуюсумму на выходе,Блок 4 сравнения находит усеченныйдекодер кода Рида-Маллера,.давший максимальную сумму, и кодирует номер этого декодера кода Рида -Маллера тремя 20двоичными символами,Регистр 5 представляет собой шестнадцатиразрядный буферный регистр,Усеченный декодер кода Рида-Маллера (фиг, 2) представляет собой декодер кода Рида-Маллера, декодирующий впределах кодового расстояния, содержащий блоки 6 сложения-вычитания, блоки7 суммирования модулей, блоки 8 сравнения (с восемью), блоки 9 ключей,блок 10 определения знака числа,30Блок сложения и вычитания для 1-гоэтапа (1=1,4) содержит 24 , сумматоров и 2 ч 3 вычитателей,Блок сложения модулей 1 -го этапапредставляет собой 2-входовой сумматор,Блок сравнения с восемью представляет собой набор пороговых логическихсхем, срабатывающих при достижении порога (порог равен восьми),40Блоки ключей выполнены на базе логических схем И, ИЛИ, НЕ и служатдля пропускания на следующий этап соответствующей группы символов,Блок определения знака числа пропускает на выход знаковый бит числа,Алгоритм работы заключается в следующем, Известно, что радиус покрытиякода Нордстрома-Робинсона равен четы",рем, тогда как радиус покрытия кода 50Рида-Маллера длины 16 равен шести, поэтому нет необходимости применятьустройство декодирования кодов РидаМаллера, работающее по максимумуправдоподобия и исправляющее ошибки 55кратности шесть включительно. Достаточно построить устройство, декодирующее код Рида-Маллера длины 16 в пре-,++ аз+ а а+а+ ао++ак 1 в=а, а Д+а+ а в = а, + а+ а+ ав =а,+ ау+,+ац+ в 4 а 1 ааа 61" 7 173600 формационный символ. Поясним это с помощью граФ-схемы (Фиг, 3). Докажем, что устройство будет ис-правлять все ошибки кратности 1,2,3,где а= +1 " символы, пришедшие иэканала, Легко видеть, что искажение 151"го символа влечет уменьшение любойсуммы на 2 (если ни один символ небыл искажен, то все суммы равны шест"надцати), искажение символов влечетуменьшение любой суммы, т,е. если ис"кажено не более трех символов, то любая сумма будет больше восьми и декодирование будет правильным, Таким образом, видно, что усеченный декодергарантированно исправляет любые три 25ошибки, При этом число сумматоровуменьшается в одном декодере кода Рида-Иаллера с 64 до 41, а во всем декодере кода Нордстрома-Робинсона с 512до 312, В декодере по максимуму правдоподобия необходимо найти максимальный элемент из 16 элементов, для этого требуется провести 15 операцийсравнения в декодере кода Рида-Маллераи 120 операций сравнения в декодерекода Нордстрома-Робинсона, в усечен 35ном декодере кода Рида-Маллера требуется четыре операции сравнения с константой и 32 операции сравнения с константой в декодере кода Нордстрома-Робинсона. Можно оценить уменьшение ап"паратурных затрат в 1,5 раза,Устройство работает следующимобразом,Кодовый вектор длины 16 приходитиз линии связи и поступает на входыблоков 1 сложения с образующими смежных классов, с выходов которых ре"зультаты поступают на входы усечен".ных декодеров 2 кода Рида-Маллера (по Оскольку один из образующих смежныхклассов состоит из одних нулей, то вэтом случае можно декодируемый вектор,сразу подать на усеченный декодер 21кода Рида-Иаллера). На вь 1 ходах усе 55ченных декодеров 2 кода Рида-Маллераимеем по пять информационных симво"лов и максимальный коэффициент корреляции. В блоке ч сравнения подкодов 8Так как код Рида-Иаллера - линейный,то беэ потери общности можно полагать,что передавался вектор, состоящий иэодних единиц. Тогда на шагах 14будем иметь соответственно; находим больший из коэффициентов кор"реляции, что дает три информационныхсимвола, которые поступают на вторыевходы регистра 5 записи декодированного слова, С.усеченного декодера 2,давшего наибольший коэффициент корреляции, пропускаем пять информационныхсимволов на первые входы регистра 5записи декодированного слова.Таким образом, получаем устройстводля декодирования кода НордстромаРобинсона, содержащее меньшее количество логических элементов по сравнению с известным устройством, работающее как комбинационная схема в отличие от известного устройства и обеспечивающее исправление всех возможныхошибок,Формула изобретения 1, Устройство для декодирования кода Нордстрома-Робинсона в дискретном канале, содержащее блок сравнения, выходы которого соединены с управля- ющими входами блока ключей, о т л йч а ю щ е е с я тем, что, с целью повышения корректирующей способности и быстродействия устройства, в него введены первый"восьмой усеченные декодеры кода Рида-йаллера, выходной буферный регистр и первый - седьмой блоки сложения с образующими смежно" го класса, входы которых и входы пер" вого усеченного декодера кода РидаМаллера соответственно объединены и являются входами устройства, выходыпервого - седьмого блоков сложения с образующими смежного класса подклю-. чены к входам соответственно второго восьмого усеченных декодеров кода Рида"Иаллера, первые " пятые выходы всех усеченных декодеров кода РидаИаллера соединены с .соответствующими информационными входами блока ключей, выходы которого соединены с первыми9 173600 входами выходного буферного регистра, вторые входы которого подключены к выходам блока сравнения, шестые выхо" ды всех усеченных декодеров кода РидаИаллера., соединены с входами блока сравнения, выходы выходного буферного регистра являются выходами устройства,2. Устройство по и. 1, о т л ич.а ю щ е е с я тем, что усеченный декодер кода Рида-Иаллера содержит ,блоки сложения-вычитания, блоки суммирования модулей, блоки сравнения, блоки ключей и блок определения знака числа, входы первого блока сложения-вычитания являются входами декодера, первые выходы первого-третьего блоков сложения-вычитания соединены с первыми информационными входами одноименных блоков ключей и входа р ми одноименных блоков суммирования модулей, выход каждого блока суммирования модулей подключен к входу одноименного блока сравнения, вторые выходы первого " третьего блоков сложения-вычитания соединены с вторыми 8 10информационными входами одноименныхблоков ключей, выходы которых подключены к входам соответственно второгочетвертого блоков сложения-вычитания,первый выход четвертого блока сложения-вычитания соединен с входом четвертого блока сравнения и первым информационным входом четвертого блокаключей, второй выход четвертого блокасложения-вычитания подключен к второмуинформационному входу четвертого блока ключей, прямые выходы первогочетвертого блоков сравнения соединеныс первыми управляющими входами одноименных блоков ключей и являютсясоответственно первым - четвертым вы"ходами декодера, инверсные выходы первого - четвертого блоков сравненияподключены к вторым управляющим входам одноименных блоков ключей, выходблока определения знака числа является . пятым выходом декодера, выходчетвертого блока ключей соединен свходом блока определения знака числаи является шестыч выходом декодера, 3 73 Ь 0081736008 г Ашихми оставительехред М.Дид йекмар упица Корреект акто пи при ГКНТ СССР роизводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10 я,Заказ 182 Ь Тираж ВНИИПИ Государственного комитета по изобретениям и о 113035, Иосква, 3-35Раушская наб