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

со

00

00 ел

о

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

Целью изобретения является повышение, достоверности функционирования устройства.

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

кодовое расстояние которого

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

На фиг. 1 представлена блок-схема yctpoftcTBa для исправления ошибок; на фиг. 2 - корректор;на фиг. 3 блок обнаружения двойной ошибки; на фиг. 4 - Локализатор oшибkи;нa фиг. 5 - вычислитель взвешенной суммы по модулю два;на фиг. 6 - формирователь проверочных элементов;на фиг, 7 - генератор импульсов;на фиг. 8 - временные диаграммы генератора импульсов; на фиг. 9 - счетчик; на фиг, 10 - блок контроля нечетности..

Устройство для исправления ошибок (фиг, 1) содержит корректор 1, блок 2 обнаружения двойной ошибки, лока- лизатор 3 ошибки, формирователь 4 проверочных элементов, генератор 5 импульсов, счетчик 6, блоки 7 и 8 памяти, блок 9 контроля нечетности элемен т НЕ 10, сумматор 11 по модулю два, дешифраторы 12 и 13, элемент ИЛИ 14, элемент И 15,

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

Блок обнаружения двойной ошибки (фиг. 3) содержит, (п-1)-разрядную схему контроля четности, где п - дли- на кода, 1 - длина дополнительной части проверочной комбинации.

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

Г п - 1 - k - 1.

Вь1числитель взвешенной суммы по одулю два (фиг, 5) содержит п элементов 2И и п- разрядный сумматор по одулю два.

Формирователь проверочных элементов (фиг, 6) содержит 1 вычислителей взвешенной суммы по модулю два (фиг. 5).

Генератор (фиг. 7) содержит задающий генератор, собранный на четырех элементах 2И-НЕ (D 1.1-D 1.4), буферный элемент D2 и 1К-триггер D3.

Счетчик (фиг, 9) содержит несколько последовательно соединенных четырехразрядных счетчиков.

Блок 9 (фиг. 10) содержит 1 трех- входовых схем контроля нечетности и 1-входовый элемент ИЛИ.

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

В исходном состоянии (фиг. 1), перед началом работы, на выходах блока 2 обнаружения двойной ошибки,ло- кализатора 3 ошибки и формирователя 4 проверочных элементов сигналы равны нулю, Счетчик 6 установлен в .нулевое состояние.Сигналы на выходах дешифраторов 12 и 13 отсутствуют. При поступлении по входным шинам не содержащей ошибок .информации она без изменений проходит через коррек

тор 1 на выходные шины устройства.

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

входы подается нулевой код с выходов счетчика 6, находящегося в нулевом состоянии,В блоке 8 памяти по адресу, равному коду на выходе сумматора 11 по модулю два, выбирается соответствующая проверочная комбинация и подается на вход блока 9 контроля нечетности, на втором входе которого установлена проверочная комбинация, сформированная в формирователе 4 в соответствии с дополнительной к коду Хэмминга матрицей. На. третьем входе блока 9 контроля нечетности сигналы отсутствуют, так как в случае одиночной ошибки счетчик 6 находится в нулевом состоянии и блок 7 памяти не работает. Поскольку произошла одна ошибка, проверочные комбинации на входах блока 9 контроля нечетности совпадают и сигнал на его выходе равен нулю. Единичный сигнал с выхода элемента НЕ 10 отпирает элемент И 15. Одновременно код номера искаженного разряда с выхода сумматора 11.по модулю два расшифровывается дешифратором 12, ив корректоре 1 происходит исправление искаженного разряда путем его инверсии (сложение по модулю два с единичным сигналов с соответствующего выхода дешифратора) . Счетчик 6 остается в нулевом состоянии, и на выходах дешифратора 13 сигналы отсутствуют.

При появлении на входах устройства информации, содержащей двойную ошибку, локализатор 3 ошибки в соответствии со способом локализации ошибки в коде Хэмминга формирует на своих выходах двоичный код, равный сумме по модулю два кодов номеров обоих искаженных разрядов, и, следовательно, не соответствующий ни одному из этих разрядов. Единичный сигнал с блока 2 обнаружения двойной ошибки одновременно с единичными сигналами на тактовом входе устройства и выходе блока 9 контроля нечетности разрешает работу генератора 5 и счетчика 6, который на своих выходах последовательно формирует двоичные коды, соответствующие позициям принятой комбинации, начиная с О до п-1 включительно (п - количество разрядов в комбинации), согласно проверочной матрице кода Хэмминга, Код с выхода счетчика 6 поступает в блок 7 памяти, где используется для выбора проверочной комбинации, соответствующей данному разряду, а так же сумматора 11 по модулю два. На другой вход сумматора 11 по модулю два поступает код с выхода локализатора 3 ошибки. Резуль

5

0

5

0

5

0

5

0

5

тат суммирования на выходе сумматора 11 по модулю, являющийся кодом предполагаемого номера позиции второго искаженного разряда, поступает в блок 8 памяти, где используется для выбора проверочной комбинации,соответствующей этому разряду. Коды проверочных комбинаций поступают в блок 2 контроля нечетности, где поразрядно складываются по модулю два друг с другом и с кодом на выходе формирователя 4, который равен сумме по модулю два строк дополнительной матрицы, соответствующих искаженным разрядам. Если номера позиций ошибок оп- ределены неверно, то код на входе элемента ИЛИ блока 9, равный сумме по модулю два кодов четырех строк дополнительной матрицы, отличен от- нуля, следовательно, сигнал на выходе блока 9 не райен нулю, элемент И 15 заперт нулевым сигналом с выхода элемента НЕ 10, счетчик 6 продолжает работу. Когда на выходе счетчика 6 появляется код номера позиции одного из искаженных разрядов, на выходе сумматора 11 по модулю два формируется код номера позиции второго искаженного разряда, сигнал на выходе блока 9 контроля нечетности становится нулевым, отпирается элемент И 15. Номера обоих искаженных разрядов расшифровываются дешифраторами 12 и 13 и через открытый элемент И 15 поступают в корректор 1, где происходит исправление ошибок. Формула из.обретения: Устройство для исправления оши--. бок, содержащее локализатор ошибки, вход которого объединен с входом блока Обнаружения двойной ошибки и первым входом корректора и является информационным входом устройства,выход локализатора ошибки соединен с первым входом сумматора по модулю два, выход которого соединен с входом первого дешифратора,выход которого соединен с первым входом эле- м.ента ИЛИ, второй дешифратор,выход которого соединен с вторым входом элемента ИЛИ,выход корректора является выходом устройства, отличающееся тем,что,с целью по- вьш1ения достоверности функционирования устройства, в него введены счетчик, элемент И, формирователь проверочных элементов кода, блоки памяти элемент НЕ, блок контроля нечетности и генератор импульсов, первьш вход которого объединен с первым входом счетчика и является тактовым входом устройства, выход блока обнаружения двойной ошибки соединен с входом генератора импульсов,выход которого соединен с вторым входом счетчика, выход которого соединен с вторым входом сумматора по модулю два, взводом второго дешифратора и входом первого блока памяти, выход которого соединен с первым входом блока контроля нечетности,выход которого соединен с третьим входом гене-

ратора импульсов и входом элемента НЕ, выход которого соединен с первым входом элемента И,выход элемента ИЛИ соединен с вторьм входом элемента И,выход которого соединен с вторым входом корректора, вход формирователя проверочных элементов кода соединен с информационным входом устройства, выход - с вторым входом блока контроля нечетности, третий вход которого соединен с выходом второго блока памяти, вход которого соединен с выходом сумматора по модулю два.

Изобретение относится к цифровой вычислительной технике и передаче информации. Целью изобретения является повьшение достоверности устройства. Поставленная цель достигается за счет обеспечения исправления двойных ошибок в коде Хемминга,кодовое расстояние которого увеличено до пяти с помощью дополнительных проверочных элементов. Для исправления случайных двойных ошибок в устройство введены формирователь проверочных элементов 4, генератор импульсов 5, счетчик 6, два блока памяти 7,8, блок контроля нечетности 9 и элемент НЕ 10. 10 ил. i (Л

Вх. инф.

Физ.2

Фиг.д

Фиг.1

.J

Фи2.5

мф.

Т и. сёл. 9

тттттттттп

Фиг.6

Фи2.1

ллял

fe.

Фиг. 9

CfA.7

Фиг. 1(3