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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (59 4 Н 03 М. 13/00

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

t ф-, ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н A BTOPCHOMV СВИДЕТЕЛЬСТВУ йа,, (21) 4099503/24-24 (22) 28.07.86 (46) 23.03,88, Бюл. № 11 (71) Воронежский политехнический институт (72) Б,В.Матвеев, А.N.×åðíåíêî, В.В.Кретинин и Е.Д.Алперин (53) 681.325(088.8) (56) Авторское свидетельство СССР № 572829, кл. С 08 С 25/00, 1975.

° Авторское свидетельство СССР

¹ 721817, кл, G 06 С 11/00, 1980.

Ьвиб (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИВ0К

„„SU„„1383509 А1 (57) Изобретение относится к цифровой вычислительной технике и передаче информации. Целью изобретения является повышение достоверности устройства. Поставленная цель достигается за счет обеспечения исправления двойных ошибок в коде Хемминга,кодовое расстояние которого увеличено до пяти с помощью дополнительных проверочных элементов. Для исправления случайных двойных ошибок в устройство введены формирователь проверочных элементов 4, генератор импульсов

5, счетчик 6, два блока памяти 7,8, блок контроля нечетности 9 и элемент

НЕ 10. 10 ил.

1 138

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

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

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

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

Устройство для исправления ошибок (фиг. 1) содержит корректор 1, блок

2 обнаружения двойной ошибки, локализатор 3 ошибки, формирователь 4 проверочных элементов, генератор 5 импульсов, счетчик 6, блоки 7 и 8 памяти, блок 9 контроля нечеткости элемент HE 10, сумматор 11 по модулю два, дешифраторы 12 и 13, элемент

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

3509

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

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

10 комбинации с соответственно установленными весовыми коэффициентами

r = n - 1 - k - 1

Вычислитель взвешенной суммы по

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

20 взвешенной суммы по модулю два (фиг. 5).

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

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

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

1-входовый элемент ИЛИ.

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

В исходном состоянии (фиг. 1), перед началом работы, на выходах блока 2 обнаружения двойной ошибки,локализатора 3 ошибки и формирователя

4 проверочных элементов сигналы равны нулю, Счетчик 6 установлен в

40 .нулевое состояние. Сигналы на выходах дешифраторов 12 и 13 отсутствуют.

При поступлении по входным шинам не содержащей ошибок информации она без изменений-проходит через коррек45 тор 1 на выходные шины устройства.

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

20

35

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

И 15. Одновременно код номера искаженного разряда с выхода сумматора

11.по модулю два расшифровывается дешифратором 12, и в корректоре 1 происходит исправление искаженного разряда путем его инверсии (сложение по модулю два с единичным сигналов с соответствующего выхода де,шифратора). Счетчик 6 остается в нулевом состоянии, и на выходах дешифратора 13 сигналы отсутствуют.

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

11 по модулю два поступает код с выхода локализатора 3 ошибки. Результат суммирования на выходе сумматора

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

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

И 15 заперт нулевым сигналом с выхода элемента НЕ 10, счетчик 6 продолжает работу. Когда на выходе счетчика 6 появляется код номера позиции одного из искаженных разрядов, на выходе сумматора 11 по модулю два формируется код номера позиции второго искаженного разряда, сигнал на выходе блока 9 контроля нечетности становится нулевым, отпирается элемент И 15. Номера обоих искаженных разрядов расшифровываются дешифраторами 12 и 13 и через открытый элемент И 15 поступают в корректор 1, где происходит исправление ошибок.

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

Устройство для исправления оши-, бок, содержащее локализатор ошибки, вход которого объединен с входом блока обнаружения двойной ошибки и первым входом корректора и является информационным входом устроиства,выход локализатора ошибки соединен с первым входом сумматора по модулю два, выход которого соединен с входом первого дешифратора,выход которого соединен с первым входом элемента ИЛИ, второй дешифратор, выход которого соединен с вторым входом элемента ИЛИ,выход корректора является выходом устройства, о т л и— ч а ю щ е е с я тем,что,с целью повьппения достоверности функционирования устройства, в него введены счетчик, элемент И, формирователь проверочных элементов кода, блоки памяти,элеменг НЕ, блок контроля не1383509 четности и генератор импульсов, первый вход которого объединен с первым входом счетчика и является тактовым входом устройства, выход блока обнаружения двойной ошибки соединен с входом генератора импульсов, выход которого соединен с вторым входом счетчика, выход которого соединен с вторым входом сумматора по модулю два, входом второго дешифратора и входом первого блока памяти, выход которого соединен с первым входом блока контроля нечетности,выход которого соединен с третьим вхоцом гене(ратора импульсов и входом элемента

НЕ, выход которого соединен с первым входом элемента И,выход элемента

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

1

) t383509

Фиг.У

Риг. 5

I

I

I д

-Ю-1

1383 .09

Риг. 7

7р бл.

Яаг. 0

1 383509! 383509

Составитель С.Берестевич

Техред N.Õoäàíè÷ Корректор О.Кундрик

Редактор Л.Лангазо

Заказ 1351/55 Тираж 928

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий.

113035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное

Производственно-полиграфическое предприятие, r. Ужгорол, ул. Проектная, 4