Устройство для исправления ошибок
Изобретение относится к вычислительной технике. Его использование в системах передачи информации при больших уровнях помех позволяет повысить корректирующую способность устройства. Это достигается благодаря разбиению перестановочного кода (48, 24) на подмножества и составлению таблицы покрытий, в соответствии с которой происходит минимизация ошибок, после чего осуществляется мажоритарное декодирование. Устройство содержит входной накопитель 1, генератор 2 ошибок, блок 3 управления, узлы 4 минимизации ошибок, блок 5 мажоритарных элементов, элемент ИЛИ 6, блок 7 выходных ключей. 1 -4-6-3-2-4-S-7, 3-1,3-5, 6-7. 2 з.п. ф -лы, 3 ил., 1 табл.
(19) (11) союз советских
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
1 (21) 4794248/24 (22) 11 12,89 (46) 23.07,92, Бюл. М 27 (71) Омский институт инженеров железнодорожного транспорта (72) В.Г.Бердичев и В.Г;Шахов (56) АВтОрСКОЕ СВИдвтЕЛЬСтВО СССР "
t4 1269272, кл. H 03 М 13/00, 1984.
Авторское свйдетельство СССР
М 1162053, кл. Н 03 М 13/00, 1983. (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ
ОШИБОК (57) Изобретенив относитСя к вычислительной технике. Его использование в системах
У
3 ил., 1 табл.
1750061
Устройство относится к вычислитель- . Устройство содержит входной накопиной технике и может быть использовано в тель 1, генератор 2 ошибок;. блок 3 управле.системах передачи информации при боль- ния; узлы 4.1 — 4.6 минимизации ошибок; ших уровнях помех. блок 5 мажоритарных элементов; элемент
5 ИЛИ 6; блок 7 выходных ключей; блоки 8 — 11
Известно устройство перестановочного сумматоров по модулю два; формирователь декодйрования, содержащее блок миними- 12 проверочных разрядов; блок 13 элеменэации ошибок, буферный регистр и схему тов ЗАПРЕТ; блок 14 сравнения; счетчик 15, исправления ошибок.. дешифратор 16.Однако оно имеет недостаточную кор- 10 В таблице покрытий ливиями показаны ректирующую способность при значитель- места информационных разрядов для кажной избыточности; кроме того оно не может дого из шести покрывающих множеств. выдавать кодовые комбинации раньше пол- На чертежах представлена разновид- . ного цикла .;; ........ ность устройства для кода (48,24).
Иэ известных устройств наиболее бли- 15 Входной накопитель 1своими Квйходазок по структуре дешифратор, содержащий ми (К вЂ” число подмножеств, яа которые раэвходной накопитель, блокуправления, гене- бивается входное кодовое слово, на фиг.1 ратор ошибок и выходные ключи, причем К = 4) связан с входами каждого из и узлов
- генератор ошибок формирует такую после- 4 минимизации ошибок, где п — число выдовательность одиночных ошибок, которая 20 бранных покрытий для входного кода (фиг.1 в конце цикла приводит к исправлению ко- и 4 число покрытий равно 6), Первые выходы да..: .:: - ": блоков 4 минимизации ошибок соединены с
Недостаток этого дешифратора — виз-: n входами блока 5 мажоритарных элеменкая корректирующая способность при боль- тов, а вторые через элемент ИЛИ 6 — с втошой длительности цикла (исправляются 25 рым входом выходных ключей 7, первый одиночные и обнаруживаются многократ- входкоторыхприсоединенквыходублока5 ные ошибки за 2п + 2 такта, где n — число. мажоритарных элементов. Разрешающий разрядов кода). ": . ..; ..: вход блока 5 мажоритарных элементов при-
Цель изобретения — повышение коррек- соединен к третьему выходу блока 3 управтируюшей способности устройства. 30 ления вместе с входом обнуления входного
Цель достигается дополнительным вве- накопителя 1, Первые два выхода блока 3 дением узлов минимизации ошибок, блока управления присоединены к первому и etoмажоритарных элементов и элемента ИЛИ, рому входам генератора 2 ошибок. Тактовые причемчетыревыходавходногонакопителя входы блока 3 управления и генератора 2 присоединеныкчетыремвходамкаждогоиэ 35 ошибок объединены и являются тактовым узлов минимизации ошибок в соответствии входом устройства.. стаблицей покрытий,,к пятым и шестым . Устройство работает следующим обравходам которых подключены первый и вто- зом. рой выходы генератора ошибок; их первые Предварительно выбранный базовый выходы связаны с входами блока мажори- 40 код (48,24) разбивается на 4 подмножества тарных элементов, а вторые их выходы че- по 12 разрядов в каждом. После этого сорез схему ИЛИ соединены с вторыми ставляется таблица покрытий таким обвходами выходных ключей. Вход блокауп- разом, чтобы с возможно меньшим равлевия соединен с выходом схемы ИЛИ, количеством перестановок выявить как второй его выход подключен к второму sxo- 45 можно большее количество ошибок, Известду генератора ошибок, а третий его вход- к но, что для кода (48,24) максимально возвторому входу входного накопителю и к - можное количество покрытий равно 92, седьмому входу блока мажоритарных эле- Выбирается 6 возможных покрытий (фиг.4), ментов. .. - : при которых код может исправлять до 5
Введение дополнительных блоков по- 50 ошибок. В соответствии с таблицей четыре вышает корректирующую способность при выхода входного накопителя 1 присоединесравнительно небольшой избыточности ко- ны кодномуизчетырех входов узлов 4.1-4,6 да и повышенном быстродействии. Появ- минимизации ошибок. ляетсй дополнительная возможность - Работу этих блоков рассмотрим на . сокращений времени декодирования при 55 структурной схеме (фиг.2). малом числе ошибок. . Два первых входа блоков сумматоров 8
Иа фиг.1 показана общая структура ус- и 9 соответствуют информационным разрятройства; нефиг.2-структурная схема уэлй дам по 12 разрядов на каждый вход(обознамивимизации ошибок; на фиг.З вЂ” структур- чены 1 и 2), два нижних (обозначены 3 и 4), ная схема блока управления. проверочные по 12 разрядов на каждом вхо1750061 де, При отсутствии ошибок в информационных разрядах формирователь проверочных разрядов 12 формирует на выходах блоков
10 и 11 сумматоров ноль, поскольку проверочные разряды формируются по тем же 5 правилам, что и в передающей части (в общем случае возможны и ненулевые синдромы на выходах блоков 10 и 11 сумматоров, но в любом случае их вес не больше фиксированного значения t). Если хотя бы одна 10 ошибка попадает в информационные разряды, вес синдрома на выходах блоков 10 и 11 сумматоров больше т, из-за чего срабатывает блок 14 сравнения, на выходе "Больше" которого появляется сигнал, который за- 15 крывает выход блока 13 элементов ЗАПРЕТ, Выходы блока 13 элементов ЗАПРЕТ являются первыми выходами блока 4 минимизации, а выход блока 14 сравнения — второй его выход.. .: 20
Одновременно с подачей кода тактовыми импульсами запускается счетчик 15 импульсов (фиг.3) и через первый выход дешифратора l6 запускается генератор 2 ошибок на выдачу одиночных ошибок (всего 25 их 24). Если в информационных разрядах кода произошла ошибка, то при совпадении по времени с ошибкой, выработанной генератором 2 ошибок, поступающей на входы 5 и 6 устройства, вес синдрома на выходе 30 формирователя проверочных разрядов 12 меньше t, что.и соответствует исправлению ошибки. С выхода блока 13 схемы ЗАПРЕТ исправленный код подается .через блок 5 мажоритарных элементов. Одновременно. 35 через схему ИЛИ 6 на вход счетчика с выхода "Меньше" блока 14 сравнения подается сигнал, сбрасывающий счетчик 15 в ноль, что останавливает работу блока 3 управления до прихода нового кода. 40
Если в принятом коде больше одной ошибки, ни на одном из выходов блоков 4, с элемента ИЛИ 6 сигнал не приходит, поэтому после 24 тактов счетчик 15 продолжает работу, При этом активизируется второй вы- 45 ход дешифратора 16; переключающий генератор 2 ошибок на выработку двойных ошибок. Блоки 4 работают так же, как и при
- одиночных ошибках. Всего двойных ошибок
С z4 = 144, Если и за это количество тактов 50 блоки 4 не срабатываю1., третий выход дешифратора выдает управляющий сигнал, очищающий входной накопитель 1 и по разрешающему входу открывающий блок 5 мажоритарных элементов, в котором все 55 одноименные разряды оцениваются по мажоритарному принципу, B результате общее время работы устройства не превышает 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 — число выбранных покрытий для входного кода) в соответствии с таблицей покрытий; первые и вторые выходы всех узлов минимизации ошибок соединены с соответствующими входами блока мажоритарных элементов и с соответствующими входами элемента
ИЛИ, выход которого подключен к управляющему входу блока выходных ключей и входу обнуления блока управления, второй выход которого соединен с вторым управляющим входом генератора ошибок, тактовый вход которого объединен с тактовым входом блока управления и является тактовым входом устройства, первые и вторые выходы генератора ошибок подключены к пятым и шестым входам всех узлов минимизации ошибок, третий выход блока управления соединен с входом обнуления входного накопителя и разрешающим входом блока мажоритарных элементов, выходы которого подключены к информационным входам блока ключей.
2,Устройство по п.1, о т л и ч а ю щ е ес я тем, что узел минимизации ошибок со1
1750061 держит блоки сумматоров по модулю два, формирователь проверочных разрядов, . блок элементов ЗАПРЕТ и блок сравнения, первые входы первого — четвертого блоков сумматоров по модулю два являются соответственно первыми-четвертйми входами узла, вторые входы первого и второго блоков сумматоров по модулю два являются пятыми и шестйми входами узла, выходы первого и второго блоков сумматоров ho модулю два подключены соответственно к первым и вторым разрешающим входам блока элементов ЗАПРЕТ и соответственно к первым и вторым входам формирователя проверочных разрядов, первые и вторые выходы которого соединены с вторыми входами соответственно третьего и четвертого блоков сумматоров по модулю два, выходы которых подключены к первым и вторым входам блока сравнения, выход "Больше" которого соединен с запрещающим входом
5 блока элементов ЗАПРЕТ, выход которого и выход "Меньше" блока сравнения являются соответственно первым и вторым выходами узла.
3. Устройство по п.1, о т л и ч а ю щ е е10 с я тем, что блок управления содержит дешифратор и счетчик импульсов, счетный вход и вход обнуления которого являются соответственно тактовым входом и входом обнуления блока, выходы счетчика импуль15 сов соединены. с входами дешифратора, первый- третий выходы которого являются одноименными выходами блока, 1750061
Составитель В. Шахов
Техред М.Моргентал Корректор Т. Палий
Редактор H. Химчук
Производственно-издательский комбинат "Па1ент", r. Ужгород, ул.Гагарина, 101
Заказ 2605 . Тираж : .: . Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям npie ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., 4/5
