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

(5)5 Е ИЗОБРЕТЕНИЯИДЕТЕЛ ЬСТВУВ ОПИСА КОМУ ГОСУДАРСТВЕННЬЗЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР 1(71) Омский институт инженеров железнодорожного транспорта(72) В.Г,Бердичев и В.Г;Шахов (56) Авторское свидетельство СССР " Ь 1269272, кл. Н ОЗ М 13/ОО, 1984.Авторское свйдетельство СССР Ь 1162053, кл. Н 03 М 13/00, 1983. (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБОК(57) Изобретение относитСЯ к вычислитель ной технике, Его использование в системах 2передачи информацйи при больших уровнях помех позволяет повысить корректирующую способность устройства. Это достигается благодаря разбиению перестановочного кода (48, 24) на подмножества и составлению таблицы покрытий, в соответствии с которой происходит минимизация ошибок, после чего бсущестВляется мажоритарное декодирование. Устройство содержит вход.- ной накопитель 1, генератор 2 ошибок, блок 3 управления, узлы 4 минимизации ошибок, блок 5 мажорйтарйых элементов, элемент ИЛИ 6, блок 7 выходных ключей, 1-4 - 6-3-2 - 4-5-7, 3-1, 3-5, 6-7, 2 з.п. ф -лы;3 ил., 1 табл, . фУстройство относится к вычислительной технике и может быть использовано в системах передачи информации при больших уровнях помех. Известно устройство перестановочного декодйрования, содержащее блок минимизации ошибок, буферныйрегистр и схему исправления ошибок,Однако оно имеет недостаточную кор 10 ректирующую способность при значительной избыточности; кроме того оно не может выдаватькодовые комбинации раньше полного цикла.Иэ известных устройств наиболее близок по структуре дешифратор, содержащий входной накопитель, блокуправления, генератор ошибок и выходные апачи, причем- генератор ошибок Формирует такую после 20 довательность одиночных ошибок, которая в конце цикла приводит к исправлению коНедостаток этого дешифратора - низкая корректирующая способность при большой длительности цикла (исправляются одиночные и обнаруживаются многократные ошибки за 2 п + 2 такта, где и - число разрядов кода), Цель изобретения - повышение корректируюшей способности устройства Цель достигается дополнительным введением узлов минимизации ошибок, блока мажоритарных элементов и элемента ИЛИ, причем четыре вцхода входного накопителя присоединены к четырем входам каждого иэ узлов минимизации ошибок в соответствии с таблицей покрытий, к пятым и шестым входам которых подключены первый и втотарных элементоь, а вторые их выходы через схему ИЛИ соединены с вторыми входами выходных ключей, Вход блока управления соединен с выходом схемы ИЛИ,второй его выход подключен к второму вхо ду генератора ошибок, а третий его вход- к второму входу входного накопителя и к седьмому входу блока мажоритарных элементов. Введение дополнительных блоков повышает корректирующую способность при сравнительно небольшой избыточности кода и повышенном быстродействии. Появляется дополнительная возможность сокращений времени декодирования при малом числе ошибок..Иа Фиг,1 показана общая структура устройства; нэ фиг.2- структурная схема узла минимизации ошибок; на фиг,З - структурная схема блока управления. рой выходы генератора ошибок; их первыевыходы связаны с входами блока мажори Устройство содержит входной накопитель 1, генератор 2 ошибок;. блок 3 управления; узлы 4.1 - 4.6 минимизации ошибок;блок 5 мажоритарных элементов; элементИЛИ 6; блок 7 выходных ключей; блоки 8 - 11сумматоров по модулю два; Формирователь12 проверочных разрядов; блок 13 элементов ЗАПРЕТ; блок 14 сравнения; счетчик 15,дешифратор 16В таблице покрытий ливиями показаныместа информационных разрядов для каждого из шести покрывающих множеств,На чертежах представлена разновидность устройства для кода (48,24).Входной накопитель 1 своими К выходами (К - число подмножеств, на которые разбивается входное кодовое слово, на фиг,1К = 4) связан с входами каждого из и узлов4 минимизации ошибок, где п - число выбранных покрытий для входного кода фиг.1и 4 число покрытий равно 6), Первые выходыблоков 4 минимизации ошибок соединены си входами блока 5 мажоритарных элементов, а вторые через элемент ИЛИ 6 - с вторым входом выходных ключей 7, первыйвход которых присоединен к выходу блока 5мажоритарных элементов. Разрешающийвход блока 5 мажоритарных элементов при-соединен к третьему выходу блока 3 управления вместе с входом обнуления входногонакопителя 1, Первые два выхода блока 3управления присоединены к первому и второму входам генератора 2 ошибок. Тактовыевходы блока 3 управления и генератора 2ошибок объединены и являются тактовымвходом устройстваУстройство работает следующим образом,Предварительно выбранный базовыйкод (48,24) разбивается на 4 подмножествапо 12 разрядов в каждом. После этого составляется таблица покрытий таким образом, чтобы с возможно меньшимколичеством перестановок выявить какможно большее количество ошибок; Известно, что для кода (48,24) максимально возможное количество покрытий равно 92,Выбирается 6 возможных покрытий (Фиг,4),при которых код может исправлять до 5ошибок. В соответствии с таблицей четыревыхода входного накопителя 1 присоединены к одному из четырех входов узлов 4,1-4,6минимизации ошибок.Работу этих блоков рассмотрим наструктурной схеме(фиг,2).Два первых входа блоков сумматоров 8и 9 соответствуют информационным разрядам по 12 разрядов на каждый входобозначены 1 и 2), два нижних обозначены 3 и 4),проверочные по 12 разрядов на каждом входе, При отсутствии ошибок в информационных разрядах формирователь проверочных разрядов 12 формирует на выходах блоков 10 и 11 сумматоров ноль, поскольку проверочные разряды формируются по тем же 5 правилам, что и в передающей части (в общем случае возможны и ненулевые синдромы на выходах блоков 10 и 11 сумматоров, но в любом случае их вес не больше фиксированного значения ф Если хотя бы одна 10 ошибка попадает в информационные разрядц, вес синдрома на выходах блоков 10 и 11 сумматоров больше 1, из-за чего срабатывает блок 14 сравнения, на выходе "Больше" которого появляется сигнал, который за крцвает выход блока 13 элементов ЗАПРЕТ, Выходы блока 13 элементов ЗАПРЕТ являются первыми выходами блока 4 минимизации, а выход блока 14 сравнения - второй 20 его выход Одновременно с подачей кода тактовыми импульсами запускается счетчик 15 импульсов (фиг.3) и через первый выходдешифратора 18 запускается генератор 2ошибок на выдачу одиночных ошибок(всего 25их 24). Если в информационных разрядахкода произошла ошибка, то при совпадениипо времени с ошибкой, выработанной генератором 2 ошибок, поступающей на входы 5и 6 устро 4 ства, вес синдрома на выходе 30формирователя проверочных разрядов 12меньше 1, что и соответствует исправлениюошибки. С выхода блока 13 схемы ЗАПРЕТисправленный код подается.через блок 5мажоритарных элементов. Одновременно. 35через схему ИЛИ 6 на вход счетчика с выхода "Меньше" блока 14 сравнения подаетсясигнал, сбрасывающий счетчик 15 в ноль,что останавливает работу блока 3 управления до прихода нового кода.40Если в принятом коде больше однойошибки, ни на одном из выходов блоков 4, сэлемента ИЛИ 6 сигнал не приходит, поэтому после 24 тактов счетчик 15 продолжаетработу, При этом активизируется второй выход дешифратора 16; переключающий генератор 2 ошибок на выработку двойныхошибок. Блоки 4 работают так же, как и приодиночных ошибках. Всего двойных ошибокС 24 = 144, Если и за это количество тактов 50блоки 4 не срабатьваю 1, третий выход дешифратора выдает управляющий сигнал,очищающий входной накопитель 1 и по разрешающему входу открывающий блок 5 мажоритарных элементов, в котором все 55одноименные разряды оцениваются по мажоритарному принципу,В результате общее время работы устройства не превышает 1+24+144 = 169 тактов, но выходной сигнал может появиться и раньше, Если проанализировать все возможные комбинации ошибок кратности до 6, можно убедиться, что среди пятикратньх ошибок только узлами 4 исправляется за 1 такт 50 от их общего количества, еще 25% исправляется за 24 такта, а не исправляется не больше 7 ф. С учетом вероятностей различных комбинаций ошибок среднее время 5-кратных ошибок составляет 5,3 такта, 4- кратных - 3,7 тактов, 3-кратных - 1,7 такта, а одно- и двухкратйце ошибки исправляются эа 1 такт.Установка блока 5 мажоритарных элементов позволяет еще выше поднять корреКтирующую способность декодера; исправляются за то же время все пятикратные и почти все шестикратныеошибки,Формула изобретения 1. Устройство для исправления ошибок, содержащее входной накопитель, информационный вход которого является одноименным входом устройства, блок управления, первый выход которого соединен с первым управляющим входом генератора ошибок, и блок выходных ключей, выходы которого являются выходами устройствами; о т л и - ч а ю щ е е с я тем, что, с целью повышения корректирующей способности устройства, в него введены узлы минимизации ошибок, блок мажоритарных элементов и элемент ИЛИ, первые К-е выходы К ) 2 - число подмножеств, накоторые разбивается входное кодовое слово) входного накопителя подключены к первым - К-м входам каждого из и узлов минимизации ошибок (и4 - число выбранных покрытий для входного кода) в соответствии с таблицей покрытий; первые и вторые выходы всех узлов минимизации ошибок соединены с соответствующими входами блока мажоритарных элементов и с соответствующими входами элемента ИЛИ, выход которого подключен к управляющему входу блока выходных ключей и входу обнуления блока управления, второй выход которого соединен с вторым управляющим входом генератора ошибок, тактовый вход которого обаединен с тактовым входом блока управления и является тактовь 1 м входом устройства, первые и вторые выходы генератора ошибок подключены к пятым и шестым входам всех узлов минимизации ошибок, третий выход блока управления соединен с входом обнуления входного накопителя и разрешающим входом блока мажоритарных элементов, выходы которого подключены к информационным входам блока ключей.2,Устройство по п,1, о т л и ч а ю щ е ес я тем, что узел минимизации ошибок со 1держит блоки сумматоров по модулю два, формирователь проверочных разрядов, блок элементов ЗАПРЕТ и блок сравнения, первые входы первого - четвертого блоков сумматоров по модулю два являются соответственно первыми-четвертйми входами узла, вторые входы первого и второго блоков сумматоров по модулю два являются пятыМи и шестйми входами узла, выходы первого и второго блоков сумматоров по модулю два подключены соответственно к первым и вторым разрешающим входам блока элементов ЗАПРЕТ и соответственно к первым и вторым входам формирователя проверочных разрядов, первые и вторые выходы которого соединены с вторыми входами соответственно третьего й четвертого блоков сумматоров по модулю два, выходыкоторых подключены к первым и вторымвходам блока сравнения, выход "Больше"которого соединен с запрещающим входом5 блока элементов ЗАПРЕТ, выход которого ивыход "Меньше" блока сравнения являютсясоответственно первым и вторым выходамиузла.3. Устройство по п.1, отл и ч а ю ще е 10 с я тем, что блок управления содержит дешифратор и счетчик импульсов, счетныйвход и вход обнуления которого являютсясоответственно тактовым входом и входомобнуления блока, выходы счетчика импуль 15 сов соединены с входами дешифратора,первый-третий выходы которого являютсяодноименными выходами блока,1750061 рректор Т, Палий Редактор Н. Химчу изводственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 Заказ 2605 ВНИИПИ Гос Составитель В. Шах Техред М.Моргентал Тираж.: . Подписноевенного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5