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

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

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

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

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

Датчик 3 ошибок содержит счетчик 13 импульсов, блок 14 счетчиков импульсов и элемент ИЛИ 15.

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

Первый блок 8 памяти содержит

счетчик 19 импульсов, дешифраторы 20- 22, блок 23 адресных регистров, блок 24 шинных формирователей, постоянный запоминающий блок 25, дешифратор 26.

Управляющий блок 1I содержит RS- триггер 27, элемент И 28, инвертор 29, элемент И 30, элемент ИЛИ 31, счетчик 32 микрокоманд, постоянный запоминающий блок 33 микрокоманд, регистр 34 микрокоманд, дешифратор

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

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

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

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

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

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

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

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

3

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

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

Если ни один из вторых модифици- рованных синдромов не совпадает со

ичньй код номера этой строки. Этот

код записывается в датчик 3 ошибок.

Затем по сигналу Вывод с выхода Вы

вод управляющего блока II, из второ- 30 строками проверочной матрицы, то для

го блока 12 памяти, выполненного в каждого второго модифицированного

синдрома вычисляется третий и т.д. Процедура вычисления модифицированных синдромов продолжается до тех

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

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

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

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

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

5 исправление ошибок.

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

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

Если ни один из вторых модифици- рованных синдромов не совпадает со

0

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

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

513

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

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

1-Разрядный код позиции ошибки с

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

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

n-k-разрядньш двоичный код, соответствующий соответствующей строке проверочной матрицы, поразрядно постпает на первые входы элементов И блока элементов, на вторые входы :; которых поступает сигнал с выхода элемента ИЛИ 17. На входы последнего подаются сигналы Информация и Вычисление. Причем, первый из них используется при вычислении основного синдрома, а второй - при вычислении модифицированных синдромов. При наличии единичного сигнала на выходе элемента ИЛИ 17 элементы И блока 16 элементов открываются и сигналы с их выходов подаются на входы соответствующих D-триггеров блока 18.

D-триггеры, на входы которых в данный момент поступили единицы, изО

5

0

5

0

5

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

Первый блок 8 памяти (фиг.4) перед приемом очередной кодовой комбинации устанавливается в исходное состояние. Для этого импульсом Сброс очищается счетчи:с 19. Адресные регистры блока 23 адресных регистров могут быть в произвольном состоянии. После установки на информационных входах номера позиции крайней правой единицы в синдроме поступает сигнал Запись (последовательность операции задается управляющим блоком 11). Так как счетчик 19 находится в нулевом состоянии, то сигнал Запись вызывает появление сигнала на первом выходе дешифратора 20. Этим сигналом производится запись кода номера позиции крайней правой единицы в первый регистр блока 23 адресных регистров.

Нулевое состояние счетчика 19 вызывает установку единичного потенциала на первом выходе дешифратора 22,

разрешающего работу первого шинного формирователя блока 24 шинных формирователей, который подключает к адресному входу постоянного запоминающего блока (ИЗБ) 25 выход первого адресного регистра блока 23 адресных регистров. При этом разрешается обращение к той области памяти ПЗБ 25, в которой хранятся номера строк проверочной матрицы, содержащих единицу

в определенной позиции. Для этого, при программировании ПЗБ 25 весь объем памяти разделен на страницы объемом п/2 1-разрядных слов так, что в первой странице хранятся номера

строк матрицы, содержащих единицу в первой позиции, во второй странице - номера строк, содержащих единицу во второй позиции и т.д.

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

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

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

Появление сигнала Выбор адреса (-1) вызывает уменьшение содержимо го счетчика 19 на единицу. Управляющий блок 11 (фиг.5) работает по приципу микропрограммного управления. В узле пуска, состоящем из элементов И 37 и 38 и RS-триггера 39, в исходном состоянии (перед приемом очередной кодовой комбинации) RS-триггер 39 очщен сигналом Сброс. Сигналом Коне вычисления, при условии единичного сигнала Несовпадение, RS-триггер 39 устанавливается в состояние 1. При этом открывается элемент И 37. Сигналы с Генератора 36 начинают поступать в счетчик 32, регистр 34 и дешифратор 35.

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

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

Единичный сигнал с выхода открытого элемента И 28 поступает через элемент ИЛИ 31 на вход предварительной установки счетчика 32. При этом происходит запись в счетчик 32 адреса новой микрокоманды из регистра 34. Сигналом Конец страницы RS-триггер 27 очищается. Элемент И 28 запирается и при выполнении условной команды сигнал Условие 1 не проходит на вход предварительной установки счетчика 32. В этом случае содержимое счетчика 32 наращивается на единицу сигналом с выхода элемента И 37, т.е происходит переход к следующей микрокоманде .

При выполнении микрокоманды Переход по условию совпадение вырабатывается управляющий сигнал Условие 2, поступающий на первый вход элемента И 30, на второй вход которого поступает сигнал Совпадение с выхода инвертора 29, являющийся инвертированным сигналом Несовпадение. Если сигнал Совпадение единичный, то элемент И 30 открыт и сигнал Ус- ловие 2 проходит с его выхода через элемент ИЛИ 31 на вход предварительной записи счетчика 32. Происходит переход на новую микрокоманду по адресу из регистра 34. Если сигнал Совпадение - нулевой, то элемент И 30 заперт и условного перехода не происходит. В этом случае выполняется следующая микрокоманда, т.е. содержимое счетчика 32 наращивается на единицу.

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

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

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

отличающееся тем, что.

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

Q g 0

5 о

5

о 5 д

соответств- тощим выходам формирователя проверочной последовательности, вход которого подключен к выходу блока элементов ИЛИ, вход сигнала Вычисление формирователя синдрома информационной последовательности объединен с входом сигнала Вычисление второго блока памяти и подключен к выходу сигнала Вычисление управляющего блока, выходы разрядов счетчика импульсов подсоединены к первым входам блока элементов ИЛИ, вторые входы которого объединены с информационными входами второго блока памяти и подключены к соответствующим информационным выхо- дам первого блока памяти, третьи входы блока элементов ИЛИ объединены с информационными входами датчика ошибок и подсоединены к соответст- вуюш,им выходам второго, блока памяти, вход Вывод информации которого объединен с входом Вывод информации датчика ошибок и подключен к выходу Вывод инфорь5ации управляющего блока выход Сброс которого подсоединен к входам Сброс первого и второго блоков памяти, счетчика импульсов и фор- мкрователя синдрома информационной последовательности, выходы которого подсоединены через первый преобразователь кодов к соответствующим входам Номер строки проверочной матрицы датчика ошибок, а через второй преобразователь кодов - к соответствующим информационным входам первого блока памяти, входы сигналов Запись Счет и Выбор адреса которого подключены соответственно к выходам сигналов Запись, Счет и второму выходу сигнала Выбор адреса управляющего блока, вход сигнала Конец страницы которого подключен к выходу сигнала Конец страницы первого блока памяти, а вход сигнала Несовпадение управляющего блока объединен с входом сигнала Несовпадение датчика ошибок и подключен к дополнительному выходу первого преобразователя кодов, причем выход сумматора по {модулю два является выходом устройства.

- -

/J

-

/

Фс/е. 2

г

Г

I

75

/5

7в

Сриг.З

Сигнал . Конец eapoHUW

.. гнал НеаЛпадема

Сигнал .Конец Sbivue/№nuii

,3amieb

.Счал

Тигноя,

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

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

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

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

Заказ 3399/55 Тираж 901 Подписное ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5

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