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

 

Изобретение может использоваться в системах передачи дискретной информации и обеспечивает повышение быстродействия. Устройство содержит регистр 1 сдвига, сумматор 2 по модулю два, датчик ошибок 3, счетчик 4 импульсов, формирователь 5 синдрома информационной последовательности, преобразователи-кодов 6 и 7, блоки памяти 8 и 12, блок элементов ИЛИ 9, формирователь 10 проверочной последовательности и управляющий блок П.. Принимаемая п-разрядная кодовая комбинация поступает в регистр 1 сдвига и формирователь 5. Синдром вычисляется поразрядным сложением по модулю два строк проверочной матрицы,.соответствующих единицам в принятой кодовой комбинации. С помощью счетчика 9 и формирователя 10 устанавливается . двоичная комбинация соответствующей строки проверочной матрицы. При отсутствии ошибок синдром равен нулю и принятая комбинация с регистра без изменений проходит на выход уст ройства. При одиночной ошибке в i-й позиции синдром представляет собой строку проверочной матрицы, номер которой равен i. Исправление происходит инвертированием. Поясняется выявление и исправление двух и более ошибок. 5 ил. § (Л со tc ю

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

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

РЕСПУБЛИК (50 4 Н 03 N 13/02

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

Фиг.!

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

f10 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3919997/24-09 (22) 15.05.85 (46) 30.07.87. Бюл. Р 28 (71) Воронежский политехнический институт (72) Б.В.Матвеев, А.M.Черненко, В.В.Кретинин и E.Ä.Àëïåðèí (53) 621.394.14(088.8) (56) Авторское свидетельство СССР

У 886281, кл. Н 04 ? 1/10, 1980.

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

Ф 687612, кл. Н 04 L 1/10, 1978. (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИ—

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

4 импульсов, формирователь 5 синдрома информационной последовательности, преобразователи кодов 6 и 7, блоки

„„SU„„ I 327297 А1 памяти 8 и 12, блок элементов ИЛИ 9, формирователь 10 проверочной последовательности и управляющий блок 11..

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

50

1 13272

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

Цель изобретения — повышение быстродействия.

На фиг.1 представлена структурная электрическая схема устройства для ис-1О правления ошибок; на фиг.2 — структурная электрическая схема датчика ошибок; на фиг.3 — - формирователь синдрома информационной последовательности; на фиг.4 — первый блок памяти; )r на фиг.5 — управляющий блок.

Устройство для исправления ошибок содержит регистр 1 сдвига, сумматор

2 по модулю два, датчик 3 ошибок, счетчик 4 импульсов, формирователь 5 синдрома информационной последовательности, первый и второй преобразователи 6 и 7 кодов, первый блок 8 памяти, блок 9 элементов ИЛИ, формирователь

10 проверочкой последовательности, 25 управляющий блок 11, второй блок 12 памяти.

Датчик 3 ошибок содержит счетчик

13 импульсов, блок 14 счетчиков им-. пульсов и элемент ИЛИ 15.

Формирователь 5 синдрома информационной последовательности содержит блок 16 элементов И, элемент ИЛИ 17 и блок 18 D-триггеров.

Первый блок 8 памяти содержит счетчик 19 импульсов, дешифраторы 2022, блок 23 адресных регистров, блок

24 шинных формирователей, постоянный запоминающий блок 25, дешифратор 26.

Управляющий блок 11 содержит RS- 40 триггер 27, элемент И 28, инвертор

29, элемент И 30, элемент ИЛИ 31, счетчик 32 микрокоманд, постоянный запоминающий блок 33 микрокоманд, регистр 34 микрокоманд, дешифратор 4>

35 управляющих сигналов, генератор

36 тактовых импульсов, элементы И 37 и 38, RS-триггер 39.

Устройство для исправления ошибок работает следующим образом.

Принимаемая п-разрядная кодовая комбинация (входной сигнал) поэлементно поступает в регистр 1 и формирователь 5 (фиг.1). Синдром вычисляется поразрядным сложением по моду- 55 лю два строк проверочной матрицы, соответствующих единицам в принятой кодовой комбинации. При этом двоичный номер анализируемого элемента при97. 2 нятой комбинации с выходов разрядов счетчика 4 через блок. 9 элементов ИЛИ подается на вход формирователя 10, на выходе которого устанавливается n-kразрядная двоичная комбинация соот-, ветствующей строки проверочной матрицы. По окончании приема кодовой комбинации в счетчике 4 вырабатывается сигнал окончания вычисления синдромов, который поступает в управляющий блок

11.

В случае отсутствия ошибок синдром равен нулю. При этом в управляющий блок 11 с первого преобразователя

6 кодов не поступает никаких сигналов. Управляющий блок 11 остается в исходном состоянии. Принятая комбинация с выхода регистра 1 без изменений поступает на выход устройства для исправления ошибок.

Для случая одиночной ошибки в i-й позиции синдром представляет собой строку проверочной матрицы, комер которой равен

Операция сравнения синдрома со строками проверочной матрицы осуществляется первым преобразователем 6 кодов, с выхоца "Номер строки проверочной матрицы которого в случае их совпадения в датчик 3 ошибок поступает двоичный 1-разрядный код числа. В датчике 3 ошибок формируется k-разрядный вектор ошибки, в котором все позиции, кроме i-й, равны нулю. Вектор ошибки в сумматоре 2 поэлементно складывается по модулю два с информационной частью кодовой комбинации с выхода регистра 1. При этом происходит инвертирование i-го элемента, т.е. исправление ошибки. Исправленная комбинация далее поступает на выход устройства для исправления ошибок.

Если произошло две ошибки, то синдром не совпадает ни с одной иэ строк проверочной матрицы. Это отличие устанавливается первым преобразователем

6 кодов, который при появлении запрещенной комбинации на входах формирует сигнал несовпадения, поступающий в управляющий блок 11. На выходах второго преобразователя 7 кодов появляется двоичный код номера крайней правой, отличной от нуля, позиции синдрома, поступающий в первый блок 8 памяти. На информационных выходах первого блока 8 памяти появляется 1-разрядный двоичный код номера одной из

)327297 строк транспонированной проверочной матрицы, содержащей единицу в позиции, номер которой определен в блоке 7.

Этот код сигналом !Вычисление" с вы-!! !!

5 хода Вычисление управляющего блока

11 записывается во второй блок 12 памяти и одновременно через блок 9 элементов ИЛИ поступает на вход формирователя 10. При этом на его выходах устанавливается n-k-разрядная двоичная комбинация, соответствующая данной строке проверочной матрицы, которая подается в формирователь 5.

Одновременно в формирователе 5 по сигналу !Вычисление!! происходит сложение по модулю два выбранной строки проверочной матрицы с ранее вычисленным синдромом. Полученный при этом первый модифицированный синдром пос- 20 тупает на вход первого преобразователя 6 кодов, который, в случае совпадения модифицированного синдрома с одной из строк проверочной матрицы, формирует на выходе "Номер строки 25 проверочной матрицы" 1-разрядный двоичный код номера этой строки. Этот код записывается в датчик 3 ошибок.

Затем по сигналу "Вывод" с выхода !Вы вод" управляющего блока 11, из второ- 30 го блока 12 памяти, выполненного в виде блока стековой памяти, считывается в 1-разрядный код номера строки матрицы, участвовавшей в вычислении модифицированного синдрома, являющийся в данном случае кодом номера другой искаженной позиции, и записывается в датчик 3 ошибок, в котором формируется вектор ошибки, представляющей собой k-разрядную двоичную 40 комбинацию с единицами в тех разрядах, номера которых заданы поступившими в датчик 3 ошибок командами.

Формирование вектора ошибки и исправление ошибок происходит так же, 4б как и в случае одиночной ошибки.

Если модифицированный синдром .не совпадает ни с одной из строк проверочной матрицы на управляющий блок

11 с первого преобразователя 6 кодов поступает сигнал несовпадения. В управляющем блоке 11 вырабатывается сигнал "Вычисление", по которому с ранее выбранной страницы первого блока 8 памяти считывается 1-разрядный двоичный код номера следующей строки матрицы, содержащей единицу в соответствующем разряде. Этот номер также запоминается во втором блоке 12 памяти вместо ранее записанного. Затем, в соответствии с поступившим из первого блока 8 памяти через блок 9 элементов ИЛИ кодом, формирователем

5 считывается n-k-разрядная двоичная комбинация строки проверочной матрицы и происходит вычисление нового модифицированного синдрома. Такая процедура вычисления модифицированного синдрома продолжается до его совпадения с одной из строк проверочной матрицы. После этого в соответствии с указанной процедурой, происходит исправление ошибок.

Если ни один иэ модифицированных синдромов не совпадает со строками проверочной матрицы, значит произошло более двух ошибок. В первом блоке

8 памяти на выходе "Конец страницы" формируется сигнал конца страницы, который поступает в управляющий блок

l1. Тогда для каждого первого модифицированного синдрома указанным образом в формирователе 5 происходит вычисление вторых модифицированных синдромов.

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

Процедура вычисления модифицированных синдромов продолжается до тех пор, пока какои-либо иэ S-1-х модифицированных синдромов не совпадает с одной из строк проверочной матрицы (S — количество ошибок в комбинации) либо пока не будут исследованы все возможные t-1-вые синдромы (t — кратность исправления ошибок данным кодом).

Совпадение фиксируется в первом преобразователе 6 кодов, который формирует 1-разрядный двоичный код номера соответствующей строки проверочной матрицы, являющийся номером позиции одной из ошибок в принятой комбинации. При этом во втором блоке 12 памяти записаны сигналом Вычисление !! II коды номеров строк проверочной матрицы, участвовавших в вычислении моди- . фицированных синдромов на всех этапах вычислений, которые будут,совпадать с номерами позиций остальных

S 1 ошибок в принятой комбинации. По сигналу "Вывод" управляющего блока

11 коды номеров позиций ошибок с первого преобразователя 6 кодов и вто1327297 рого блока 12 памяти, поступают в датчик 3 ошибок, в котором формируется вектор ошибки, представляющий собой k-разрядную двоичную комбинацию, с единицами в тех разрядах, номеРа 5 которых заданы поступившими в датчик ошибок кодами. Происходит исправление ошибок путем поразрядного сложения по модулю два в сумматоре 2 вектора ошибки и информационной части принятой кодовой комбинации с выхода регистра 1.

Датчик 3 ошибок (фиг.2) работает следующим образом.

1-Разрядный код позиции ошибки с входа",Номер строки проверочной матрицы" инвертированным сигналом "Несовпадение записывается в счетчик

13. Далее 1-разрядный код позиции ошибки информационных входов записы- 20 вается по сигналу Вывод" в первый счетчик блока 14 счетчиков, на выходах которого устанавливается записанный код. По следующему сигналу "Вывод" этот код переписывается во второй счетчик, а 1-разрядный код позиции ошибки записывается в первый счетчик и т.д. Далее по тактовым импульсам соответствующие счетчики начинают отсчет. В те моменты, когда количество отсчитанных тактовых импульсов совпадает с номером позиции ошибки, ранее записанном в каком-либо из счетчиков, на выходе (О этого счетчика появляется сигнал, который 35 через элемент ИЛИ 15 поступает на выход.

Формирователь 5 (фиг.3) работает следующим образом.

n-k -разрядный двоичный код, соот- 40 ветствующий соответствующей строке проверочной матрицы, поразрядно поступает на первые входы элементов И блока элементов, на вторые входы . которых поступает сигнал с выхода эле- < мента ИЛИ 17. На входы последнего подаются сигналы Информация" и "Вычисление . Причем, первый из них используется при вычислении основного синдрома, а второй — при вычислении модифицированных синдромов. При наличии единичного сигнала на выходе элемента ИЛИ 17 элементы И блока 1б

Нулевое состояние счетчика 19 вызывает установку единичного потенциала на первом выходе дешифратора 22, разрешающего работу первого шинного формирователя блока 24 шинных формирователей, который подключает к адресному входу постоянного запоминающего блока (ПЗБ) 25 выход первого адресного регистра блока 23 адресных регистров. При этом разрешается обращение к той области памяти ПЗБ 25, в которой хранятся номера строк проверочной матрицы, содержащих единицу в определенной позиции. Для этого, при программировании ПЗБ 25 весь объем памяти разделен на страницы" объемом n/2 1-разрядных слов так, что в первой "странице" хранятся номера строк матрицы, содержащих единицу в первой позиции, во второй "странице"номера строк, содержащих единицу во второй позиции и т.д. элементов открываются и сигналы с их выходов подаются на входы соответствующих D-триггеров блока )8.

D-триггеры, на входы которых в данный момент поступили единицы, изменяют свое состояние, так как о и включены в счетном режиме. При вычислении синдромов осуществляется счет числа единиц по каждому разряду синдрома. Если это число — четное, то соответствующий D-триггер очищается, а если нечетное — устанавливается. Таким образом, блок 18 D-триггеров выполняет функции накапливающего поразрядного сумматора по модулю два. Сигналом "Сброс" с блока 11 производится начальная очистка накапливающего поразрядного сумматора по модулю два, перед вычислением очередного основного синдрома.

Первый блок 8 памяти (фиг.4) перед приемом очередной кодовой комбинации устанавливается в исходное состояние. Для этого импульсом Сброс" очищается счетчи.. 19. Адресные регистры блока 23 адресных регистров могут быть в произвольном состоянии.

После установки на информационных входах номера позиции крайней правой единицы в синдроме поступает сигнал

Запись" (последовательность операции задается управляющим блоком 11).

Так как счетчик 19 находится в нулевом состоянии, то сигнал Запись" вызывает появление сигнала на первом выходе дешифратора 20. Этим сигналом производится запись кода номера позиции крайней правой единицы в первый регистр блока 23 адресных регистров.

7 1327

Сигнал "Счет", поступающий в блок

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

Затем поступает очередной сигнал

Счет" и т.д. В этом случае на выходе дешифратора 26 появляется сигнал

"Конец страницы".

По сигналу "Выбор адреса" (+"1") 15 увеличивается на единицу содержимое счетчика 19. При этом единичным потенциалом с второго выхода дешифратора 22 разрешается работа второго шинного формирователя блока 24 шин- 20 ных формирователей, т.е. к адресному входу ПЗБ подключается выход второго адресного регистра блока 23 адресных регистров.

Сигнал "Запись" вызывает появление 25 сигнала на втором выходе дешифратора

20, т.е. на входе "Запись" второго адресного регистра блока 23 адресных регистров. Аналогично, сигнал "Счет" преобразуется в сигнал на втором вы- 30 ходе дешифратора 21, т.е. на счетном входе второго адресного регистра блока 23 адресных регистров.

Появление сигнала "Выбор адреса" ("-!") вызывает уменьшение содержимо- З5

ro счетчика 19 на единицу. Управляющий блок ll (фиг.5) работает по принципу микропрограммного управления. В узле пуска, состоящем из элементов И

37 и 38 и RS-триггера 39, в исходном 40 состоянии (перед приемом очередной кодовой комбинации) КБ-триггер 39 очищен сигналом "Сброс". Сигналом "Конец вычисления", при условии единичного сигнала Несовпадение", RS-триггер 45

39 устанавливается в состояние "1".

При этом открывается элемент И 37.

Сигналы с 1 енератора 36 начинают поступать в счетчик 32, регистр 34 и дешифратор 35.

Узел выбора адреса следующей микрокоманды состоит из RS — триггера 27, элементов И 28 и 30, инвертора 29, элемента ИЛИ 31 и счетчика 32. При появлении безусловных команд содержимое счетчика 32 (адрес микрокоманды) наращивается на единицу по сигналу с выхода элемента И 37. B случае условной команды возможны два ва297 рианта: переход к следующей микрокоманде (наращивание содержимого счетчика 32 на единицу), если некоторое условие не выполняется, или переход по адресу из регистра 34 (загрузка в счетчик 32 адреса новой микрокоманды из регистра 34),если это условие выполнено. В данном случае условием, вызывающим переход на новый адрес, является отсутствие сигналов

"Несовпадение" и "Конец страницы".

RS-триггер 27 служит для фиксации сигнала "Конец страницы". его основное состояние "1" на выходе, установленная сигналом Запись". При выполнении команды "IIepexop по условию конец страницы вырабатывается управляющий сигнал "Условие 1", который поступает на первый вход элемента И 28, на второй вход которого подан единичный потенциал с выхода RS-триггера 27.

Единичный сигнал с выхода открытого элемента И 28 поступает через элемент ИЛИ 31 на вход предварительной установки счетчика 32. При этом происходит запись в счетчик 32 адреса новой микрокоманды из регистра 34.

Сигналом Конец страницы" RS-триггер

27 очищается. Элемент И 28 запирается и при выполнении условной команды сигнал "Условие 1" не проходит на вход предварительной установки счетчика 32. В этом случае содержимое счетчика 32 наращивается на единицу сигналом с выхода элемента И 37, т.е. происходит переход к следующей микрокоманде.

При выполнении микрокоманды "IIepe ход по условию совпадение" вырабатывается управляющий сигнал "Условие

2", поступающий на первый вход элемента И 30, на второй вход которого поступает сигнал Совпадение" с выхода инвертора 29, являющийся инвертированным сигналом Несовпадение".

Если сигнал "Совпадение" единичный, то элемент И 30 открыт и сигнал "Условие 2" проходит с его выхода через элемент ИЛИ 31 на вход предварительной записи счетчика 32. Происходит переход на новую микрокоманду по адресу из регистра 34. Если сигнал

Совпадение — нулевой, то элемент

И 30 заперт и условного перехода не происходит. В этом случае выполняется следующая микрокоманда, т.е. содержимое счетчика 32 наращивается на единицу.

1327297

Выполнение каждой микрокоманды начинается с записи кода микрокоманды в регистр 34. При этом адрес микрокоманды с выхода счетчика 32 поступа5 ет на вход постоянного запоминающего блока 33, на выходе которого устанавливается код микрокоманды. Далее по сигналу с выхода элемента И 37 этот код записывается в регистр 34.

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

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

Устройство для исправления ошибок, 25 содержащее последовательно соединенные датчик ошибок и сумматор по модулю два, а также регистр сдвига и формирователь проверочной последовательности, причем информационксый вход ре— гистра сдвига и объединенный тактовый вход регистра сдвига и датчика ошибок являются соответственно информационным и тактовым входами устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, введены последовательно соединенные счетчик импульсов, управляющий блок и первый блок памяти, а также блок элементов ИЛИ, формирователь синдрома ин-4О формационной последовательности, первый и второй преобразователи кодов и второй блок памяти, при этом тактовый вход счетчика импульсов подключен к тактовому входу регистра сдвига, выход которого подсоединен к второму входу сумматора по модулю два, информационный вход и входы проверочной последовательности формирователя синдрома информационной последовательнос-50 ти подключены соответственно к информационному входу регистра сдвига и оответствующим выходам формирователя проверочной последовательности, вход которого подключен к выходу блока элементов ИЛИ, вход сигнала Вычисление" формирователя синдрома информационной послецовательности объединен с входом сигнала Вычисление" второго блока памяти и подключен к выходу сигнала "Вычисление" управляющего блока, выходы разрядов счетчика импульсов подсоединены к первым входам блока элементов ИЛИ, вторые входы которого объединены с информационными входами второго блока памяти и подключены к соответствующим информационным выходам первого блока памяти, третьи входы блока элементов ИЛИ объединены с информационными входами датчика ошибок и подсоединены к соответствующим выходам второго блока памяти, вход "Вывод информации" которого объединен с входом "Вывод информации1 датчика ошибок и подключен к выходу

"Вывод информации управляющего блока, выход "Сброс которого подсоединен к входам "Сброс первого и второго блоков памяти, счетчика импульсов и формирователя синдрома информационной последовательности, выходы которого подсоединены через первый преобразователь кодов к соответствующим входам "Номер строки проверочной матрицы" датчика ошибок, а через второй преобразователь кодов — к соответствующим информационным входам первого блока памяти, входы сигналов "Запись

"Счет" и "Выбор адреса" которого подключены состветственно к выходам

c»r;-|алов Запись 1, 1Счет и второму выходу сигнала "Выбор адреса" управляющего блока, вход сигнала "Конец

""òðàíèöû которого подключен к выходу сигнала "Конец страницы" первого блока памяти, а вход сигна.ла "Несовпадение" управляющего блока объединен с входом сигнала "Несовпадение" датчика ошибок и подключен к дополнительному выходу первого преобразователя кодов, причем выход сумматора по модулю два является выходом устройства.

1327297

Фие. 2

1327297 в:иаМвд едю

@вьем

Гиаю

Фг, йвсо5п

uaw

Юлю

Уынаж

Составитель В.Орлов

Техред Л.Сердюкова Корректор В.Бутяга

Редактор И.Касарда

Заказ 3399/55 Тираж 901 Подписное

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

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

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