Устройство для исправления ошибок Советский патент 1992 года по МПК H03M13/00 

Ё

Изобретение относится к вычислительной технике. Его использование в системах передачи информации при больших уровнях помех позволяет повысить корректирующую способность устройства. Это достигается благодаря разбиению перестановочного кода (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 табл.

VI

ся о о о

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

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

Однако оно имеет недостаточную корректирующую способность при значительной избыточности; кроме того оно не может выдавать кодовые комбинации раньше полного цикла.

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

Недостаток этого дешифратора - низкая корректирующая способность при большой длительности цикла (исправляются одиночные и обнаруживаются многократные ошибки за 2п + 2 такта, где п - число разрядов кода).

Цель изобретения - повышение корректирующей способности устройства.

Цель достигается дополнительным введением узлов минимизации ошибок, блока мажоритарных элементов и элемента ИЛИ, причем четыре выхода входного накопителя присоединены к четырем входам каждого из узлов минимизации ошибок в соответствии с таблицей покрытий, к пятым и шестым входам которых подключены первый и второй выходы генератора ошибок; их первые выходы связаны с входами блока мажоритарных элементов, а вторые их выходы через схему ИЛИ соединены с вторыми входами выходных ключей. Вход блока управления соединен с выходом схемы ИЛИ, второй его выход подключен к второму входу генератора ошибок, а третий его вход - к второму входу входного накопителя и к седьмому входу блока мажоритарных элементов,

Введение дополнительных блоков повышает корректирующую способность при сравнительно небольшой избыточности кода и повышенном быстродействии. Появляется дополнительная возможность сокращений времени декодирования при малом числе ошибок.

На фиг.1 показана общая структура устройства; на фиг.2 - структурная схема узла минимизации ошибок; на фиг.З - структурная схема блока управления.

Устройство содержит входной накопитель 1, генератор 2 ошибок; блок 3 управления; узлы 4.1-4.6 минимизации ошибок; блок 5 мажоритарных элементов; элемент

ИЛИ 6; блок 7 выходных ключей; блоки 8-11 сумматоров по модулю два; формирователь 12 проверочных разрядов; блок 13 элементов ЗАПРЕТ; блок 14 сравнения; счетчик 15, дешифратор 16.

0 В таблице покрытий линиями показаны места информационных разрядов для каждого из шести покрывающих множеств.

На чертежах представлена разновидность устройства для кода (48,24).

5 Входной накопитель 1 своими К выходами (К - число подмножеств, на которые разбивается входное кодовое слово, на фиг.1 К 4) связан с входами каждого из п узлов 4 минимизации ошибок, где п - число вы0 бранных покрытий для входного кода (фиг.1 и 4 число покрытий равно 6), Первые выходы блоков 4 минимизации ошибок соединены с п входами блока 5 мажоритарных элементов, а вторые через элемент ИЛИ 6 - с вто5 рым входом выходных ключей 7, первый вход которых присоединен к выходу блока 5 мажоритарных элементов. Разрешающий аход блока 5 мажоритарных элементов присоединен к третьему выходу блока 3 управ0 ления вместе с входом обнуления входного накопителя 1. Первые два выхода блока 3 управления присоединены к первому и второму входам генератора 2 ошибок. Тактовые входы блока 3 управления и генератора 2

5 ошибок объединены и являются тактовым входом устройства.

Устройство работает следующим образом.

Предварительно выбранный базовый

0 код (48,24) разбивается на 4 подмножества по 12 разрядов в каждом. После этого составляется таблица покрытий таким образом, чтобы с возможно меньшим количеством перестановок выявить как

5 можно большее количество ошибок. Известно, что для кода (48,24) максимально возможное количество покрытий равно 92, Выбирается б возможных покрытий (фиг.4), при которых код может исправлять до 5

0 ошибок. В соответствии с таблицей четыре выхода входного накопителя-1 присоединены к одному из четырех входов узлов 4.1-4.6- минимизации ошибок.

Работу этих блоков рассмотрим на

5 структурной схеме (фиг.2).

Два первых входа блоков сумматоров 8 и 9 соответствуют информационным разрядам по 12 разрядов на каждый вход (обозначены 1 и 2), два нижних (обозначены 3 и 4). проверочные по 12 разрядов на каждом входе, При отсутствии ошибок в информационных разрядах формирователь проверочных разрядов 12 формирует на выходах блоков 10 и 11 сумматоров ноль, поскольку проверочные разряды формируются по тем же правилам, что и в передающей части (в общем случае возможны и ненулевые синдромы на выходах блоков 10 и 11 сумматоров, но в любом случае их вес не больше фиксированного значения t}. Если хотя бы одна ошибка попадает в информационные разряди, вес синдрома на выходах блоков 10 и 11 сумматоров больше t, из-за чего срабатывает блок 14 сравнения, на выходе Больше которого появляется сигнал, который закрывает выход блока 13 элементов ЗАПРЕТ, Выходы блока 13 элементов ЗАПРЕТ являются первыми выходами блока 4 минимизации, а выход блока 14 сравнения - второй его выход.

Одновременно с подачей кода тактовыми импульсами запускается счетчик 15 импульсов (фиг.З) и через первый выход дешифратора 16 запускается генератор 2 ошибок на выдачу одиночных ошибок (всего их 24). Если в информационных разрядах кода произошла ошибка, то при совпадении по времени с ошибкой, выработанной генератором 2 ошибок, поступающей на входы 5 и 8 устройства, вес синдрома на выходе формирователя проверочных разрядов 12 меньше t, что и соответствует исправлению ошибки. С выхода блока 13 схемы ЗАПРЕТ исправленный код подается через блок 5 мажоритарных элементов. Одновременно через схему ИЛИ 6 на вход счетчика с выхода Меньше блока 14 сравнения подается сигнал, сбрасывающий счетчик 15 в ноль, что останавливает работу блока 3 управления до прихода нового кода.

Если в принятом коде больше одной ошибки, ни на одном из выходов блоков 4, с элемента ИЛИ 6 сигнал не приходит, поэтому после 24 тактов счетчик 15 продолжает работу. При этом активизируется второй выход дешифратора 16, переключающий генератор 2 ошибок на выработку двойных ошибок. Блоки 4 работают так же, как и при одиночных ошибках. Всего двойных ошибок С 24 - 144, Если и за это количество тактов блоки 4 не срабатывают, третий выход дешифратора выдает управляющий сигнал, очищающий входной накопитель 1 и по разрешающему входу открывающий блок 5 мажоритарных элементов, в котором все одноименные разряды оцениваются по мажоритарному принципу,

В результате общее время работы устройства не превышает 1+24+144 169 тактов, но выходной сигнал может появиться и

раньше. Если проанализировать все возможные комбинации ошибок кратности до 6, можно убедиться, что среди пятикратных ошибок только узлами 4 исправляется за 1

такт 50% от их общего количества, еще 25% исправляется за 24 такта, а не исправляется не больше 7%. С учетом вероятностей различных комбинаций ошибок среднее время 5-кратных ошибок составляет 5,3 такта, 4кратных - 3,7 тактов, 3-кратных - 1,7 такта, а одно- и двухкратные ошибки исправляются за 1 такт.

Установка блока 5 мажоритарных элементов позволяет еще выше поднять корректирующую способность декодера: исправляются за то же время все пятикратные и почти все шестикратные ошибки.

Формула изобретения

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

него введены узлы минимизации ошибок, блок мажоритарных элементов и элемент ИЛИ, первые К-е выходы (К Ј 2 - число подмножеств, на которые разбивается входное кодовое слово) входного накопителя подключены к первым - К-м входам каждого из п узлов минимизации ошибок (п Ј. 4 - число выбранных покрытий для входного кода) в соответствии с таблицей покрытий, первые и вторые выходы всех узлов минимизации

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

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

2,Устройство по п.1, о т л и ч а ю щ е е - с я тем, что узел минимизации ошибок содержит блоки сумматоров по модулю два, формирователь проверочных разрядов, блок элементов ЗАПРЕТ и блок сравнения, первые входы первого-четвертого блоков сумматоров по модулю два являются соответственно первыми-четвертыми входами узла, вторые входы первого и второго блоков сумматоров по модулю два являются пятыми и шестыми входами узла, выходы первого и второго блоков сумматоров по модулю два подключены соответственно к первым и вторым разрешающим входам блока элементов ЗАПРЕТ и соответственно к первым и вторым входам формирователя проверочных разрядов, первые и вторые выходы которого соединены с вторыми входами соответственно третьего и четвертого

5

блоков сумматоров по модулю два, выходы которых подключены к первым и вторым входам блока сравнения, выход Больше которого соединен с запрещающим входом блока элементов ЗАПРЕТ, выход которого и выход Меньше блока сравнения являются соответственно первым и вторым выходами узла.

Фи&Ј

фае 3

If