Корректор ошибок Советский патент 1993 года по МПК G11C29/00 

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

В настоящее время в вычислительной технике при кодировании информации широкое применение получили циклические коды - коды Хэмминга, Файра и др. Помехоустойчивость указанных кодов обеспечивается за смет, введения избыточности, достигаемой посредством добавления так называемых проверочных или контрольных символов к информационным символам кодируемого сообщения. В процессе кодирования исходное сообщение разбивается на информационные слова уИкф с фиксированным числом символов и для каждого информационного слова по определенному алгоритму формируются контрольные символы .VKOHTP- После присоединения контрольных символов к информационному слову получается кодовое слово VKOR циклического блокового систематического (п, к) - кода; где п - общее количество символов в кодовом слове, k - количество информационных символов; m п - к - количество контрольных символов. При этом часто пользуются пол- иномикальным представлением кодовых векторов, что позволяет задавать циклический код математически с помощью так называемых порождающих многочленов. Например, порождающий многочлен над полем символов алфавита GF2 задает (31.26)-код Хэмминга, исправляющий одну случайную ошибку.

00

о о о

45

Формирование контрольных символов в процессе кодирования осуществляется путем вычисления остаточного многочлена VKOHTP Уинф. xmmodY с использованием арифметики полей Галуа. При приеме сообщения осуществляют его декодирование с целью обнаружения и исправления ошибок, возникающих при хранении или передаче, Принятое слово может быть представлено в виде суммы передаваемого кодового слова VKOA и вектора ошибки УОШ. Вычисление при декодировании остаточного многочлена VKOHTP (VKOA + УОШ) -xm mod Y позволяет получить контрольные символы вектора ошибки, называемые синдромом. Располагая известным значением синдрома, можно, используя специальные устройства, называемые декодерами или корректорами ошибок, сформировать вектор ошибки и воссоздать в первоначальном виде переданное кодовое слово.

Известно устройство для коррекции независимых ошибок (см.Питерсон У., Уэлдон Э. Коды, исправляющие ошибки, - М.: Мир, 1976, с. 191). Для этого корректора характерно недостаточное быстродействие, что обусловлено потерями времени на коррекцию кодовых слов, у которых искажены контрольные символы.

Этот же недостаток присущ и корректору пачек ошибок (см.Портной С.А., Анкуди- нов Д. Р. .Ко дек и корректирующих блочных кодов. - Зарубежная радиоэлектроника,

1985. №7, с. 3-27).

Известен корректор ошибок с неалгеб- раичёским последовательным декодированием символовциклического систематического кода, в частности кода Хэмминга (см.Блейхут Р.. Теория и практика кодов, контролирующих ошибки. - М.: Мир,

1986. стр. 174). Это устройство выбрано в качестве прототипа.

Схема прототипа приведена на фиг. 1. Она содержит синдромный регистр 1, блок обратной связи 2, детектор ошибки 3, блок фиксации местоположения ошибки 4, буфер данных 5, блок коррекции ошибки 6 и блок управления 7; выход блока обратной связи 2 соединен с информационным входом син- дромного регистра 1. выходы которого соединеныс соответствующими информационными входами детектора ошибки 3 и блока фиксации местоположения ошибки 4, выход которого соединен со входами коррекции блока обратной связи 2 и блока коррекции ошибки 6, выход которого подключен к выходу 17 устройства и является информационным выходом

0

5

0

5

0

5

0

5

0

5

корректора ошибок, выход детектора ошибки 3 подключен к выходу 16 устройства и является управляющим выходом корректора ошибок, информационные входы блока обратной связи 2, буфера данных 5 и первый информационный вход блока коррекции ошибки 6 объединены и подключены к входу 8 устройства, являющемуся информационным входом корректора ошибок, управляющие входы блока фиксации местоположения ошибки 4, детектора ошибки 3, блока коррекции ошибки 6 и блока обратной связи 2 подключены к управляющему выходу регистра синдрома 1, входы сброса и сдвига которого соединены соответственно с первым и вторым выходами блока управления 7, третий выход которого соединен с входом разрешения работы блока фиксации местоположения ошибки 4, второй информационный вход блока коррекции ошибки & соединен с выходом буфера данных 5, адресные входы и входы чтения, записи, обращения которого соединены соответственно с четвертым, пятым, шестым и седьмым выходами блока управления 7, восьмой, девятый и десятый выходы которого подключены к выходам 14, 15, 13 устройства и являются соответственно выходом синхронизации источника информации, выходом синхронизации приемника информации и выходом готовности корректора ошибок, входы начальной установку, сброса ошибки, чтения и коррекции блока управления подключены к входам9,10.11, 12 устройства и являются с.оответственно входом начальной установки, входом сброса ошибки, входом.чтения и входом коррекции корректора ошибок.

Синдромный регистр 1 при приеме сообщений обеспечивает формирование контрольных символов (синдрома) кодового слова, поступающего с входа 8 устройства на информационный вход блока 2 обратной связи и с выхода последнего - на информационный вход регистра 1. Формирование синдрома осуществляется посредством посимвольного деления кодового слова на по- .рождающий многочлен. Прием и деление кодового слова на порождающий многочлен начинается с его.старших символов. Остатки от деления отдельных символов накапли- ваются в синдромном регистре 1. Окончательный результат получается после приема последнего (младшего) символа кодового слова. При обнаружении ошибки и принятом сообщении (синдром не равен нулю) регистр 1 и содержащийся в нем синдром используются для построения вектора

ошибки. Это осуществляется посредством модульного умножения синдрома, что обеспечивается сдвигом вправо регистра синдрома 1. Сдвиг и сброс синдромного регистра

1 производится сигналами из блока управления 7, поступающими на входы сдвига и сброса регистра 1.

Блок 2 обратной связи обеспечивает формирование входных сигналов для синдромного регистра 1, используя для этого символы кодового слова, поступающие с входа 8 устройства, а также выходные сигналы (сигналы обратной связи), освобождающиеся при сдвиге старшего разряда синдромного регистра 1. При этом в зависимости от значения сигнала на выходе блока фиксации местоположения ошибки 4, блок

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

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

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

В блоке коррекции ошибки б происходит непосредственное исправление ошибок принятого кодового слова путем его посимвольного сложения (в случае двоичных кодов - по модулю два) с вектором ошибки,

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

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

5

сброса ошибки, осуществляющее сброс синдромного регистра 1 и подготовку к работе блока управления. Затем на вход 11 устройства приемник информации подает 5 сигнал чтения и блок управления сбрасывает сигнал готовности на выходе 13 устройства и формирует последовательность сигналов синхронизации,которые с выхода 14 поступают к источнику кодированных со0 общений. За одну команду чтения обеспечивается прием одного кодового слова. В ответ на каждый синхросигнал источник сообщений передает один символ. Эти символы ест. входа 8 корректора ошибок без изменений через блок коррекции ошибок 6 поступают на информационный выход 17 и далее - к приемнику информации в сопровождении сигналов синхронизации на выхоQ де 15 устройства. Одновременно принимаемые символы записываются в буфер данных 5 и поступают в блок обратной связи 2 для деления на порождающий многочлен. После приема очередного символа

5 блок управления 7 сдвигает вправо на.один разряд синдромный регистр 1 и инкремен- тирует на 1 код адреса на адресных входах буфера данных 5. Таким образом в процессе последовательного посимвольного деления

0 принятого кодового слова в регистре 1 накапливаются частичные остатки от деления всех символов кодового слова, образующие в конечном итоге умножений ( ( синдром ошибки S (УХОД + УОШ) хт-тойУ.

5 После приема всех п символов кодового слова блок управления 7 останавливается и выдает на выход 13 устройства сигнал готовности. Если содержимое синдромного регистра 1 в этот момент не будет равно О,

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

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

коррекции. Блок управления 7 при этом разрешает работу блока фиксации местоположения ошибки 4. переводит буфер данных 5

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

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

0

5

0

5

0

5

0

5

0

5

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

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

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

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

Предлагаемое устройство изображено на фиг. 2. Оно .содержит синдромный регистр 1, включающий одноразрядные сдвигающие регистры 2, связанные через схемьи 3 сложения по модулю два, и ключи 4 задания коэффициентов порождающего многочлена, блок обратной связи 5, детектор ошибки 9, блок фиксации местоположения ошибки 10, буфер данных 11, блок коррекции ошибки 12, блок селекции ошибок кон- трольных символов 1библокуправления 17; выход блока обратной связи 5 соединен с информационным входом синромного регистра 1. выходы которого соединены с соответствующими информационными входами детектора ошибки 9, блока селекции ошибок контрольных символов 16 и блока фиксации местоположения ошибки 10, выход которого соединен со входом коррекции блока обратной связи 5 и блока коррекции ошибки 12, выход которого подключен к выходу 27 устройства и является информационным выходом корректора ошибок, выход детектора ошибки 9 соединен с выходом 26 устройства и является первым управляющим выходом корректора ошибок, информационные входы блока обратной связи 5. буфера данных 11 и первый информационной вход блока коррекции ошибки 12 объединены и подключены к входу 18 устройства, являющемуся информационным входом корректора ошибок, управляющие входы блока фиксации местоположения ошибки 10, детектора ошибки 9, блока коррекции ошибки 12 и блока обратной связи 5 подключены к управляющему выходу регистра синдрома 1, входы сброса и сдвига которого соединены соответственно с первым и вторым выходами блока управления 17, третий выход которого соединен с входом разрешения работы блока фиксации местоположения ошибки 10, второй информационный вход блока коррекции ошибки 12 соединен с выходом буфера данных 11, адресные входы и входы чтения, записи, обращения которого соединены соответственно с четвертым, пятым, шестым и седьмым выходами блока управления 17, восьмой, девятый и десятый выходы которого подключены к выходам 24, 25, 23 устройства и являются соответственно выходом синхронизации источника информации, выходом синхронизации приемника информации и выходом готовности корректора .ошибок, входы начальной установки, сброса ошибки, чтения и коррекции блока управления 17 подключены к входам 19, 20, 21, 22 устройства и являются соответственно входом начальной установки, входом сброса ошибки, входом чтения и входом коррекции корректора ошибок, одиннадцатый выход блока управления 17 соединен с управляющим входом бло.ка селекции ошибок контрольных символов 16, выход которого -подключен к выходу 28 устройства и является вторым управляющим выходом корректора ошибок.

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

умножения синдрома при сдвигах вправо регистра синдрома 1. Сдвиг и сброс регистра 1 производится сигналами,-поступающими из блока управления 17. В случае двоичных циклических кодов для

полиномиального представления порождающего многочлена и кодового слова в виде

2, -$i x используется алфавит из двух

символов - О и 1. Соответственно коэффициенты ai многочлена также могут принимать только два указанных значения. Например, синдромный регистр для декодирования циклического кода, заданного порождающим многочленом Y x + х 1

Э| X -, 30 , 34 0,

25

i 0

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

задающих коэффициенты а0 и ai. Если коэффициенты ai постоянны, то ключи 4 могут быть фиксированными (запаянными) связями. Выходами синдррмного регистра 1 являются выходы входящих в его состав

сдвигающих регистров 2. Сигнэл с выхода старшего - крайнего справа рэзряда (управляющий выход) через блок 5 участвует в выработке . сигналов обратной связи синдромного регистра 1.

Блок 5 обратной связи содержит двух- входовую схему И7, инвертор 6 и двухвходо- вую схему сложения по модулю два 8. Блок имеет 3 входа и 1 выход. Вход инвертора.6 является входом коррекции блока 5. Один из

входов схемы И7 соединен с управляющим выходом синдромного регистра 1 и является управляющим входом блока 5. Информационным входом блока 5 является вход схемы 8 сложения по модулю два, соединенный с

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

Детектор ошибки 9 представляет собой схему И-НЕ с числом входов, равным количеству разрядов синдромного регистра 1. При наличии ошибок в принятом кодовом слое содержимое регистра синдрома 1 не будет равно 0 и детектор ошибки сформирует 1 на своем выходе, который является первым управляющим выходом устройства. В противном случае содержимое регистра синдрома 1 и выходной сигнал детектора ошибки будут равны 0.

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

Буфер данных 11 предназначен для временного хранения принятого в режиме чтения кодового слова на случай, если в дальнейшем потребуется коррекция ошибок. В качестве буфера данных удобнее всего использовать последовательный сдвигающий регистр. Однако, ввиду того, что сдвигающие регистры большей разрядности промышленностью не выпускаются, в качестве буфера данных чаще всего используют од поразрядные ЗУ с прямой выборкой. Адресные сигналы, сигналы чтения, записи и обращения к буферу данных формируются в блоке управления 17.

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

5

12 является .вход схемы И.ЛИ 15. соединенный с информационным входом 18 корректора ошибок. Второй информационный вход блока 12 образует вход схемы сложения по модулю два 14, соединенный с выходом буфера данных 11. Выход схемы ИЛИ 15 является одновременно выходом блока 12.

Блок селекции ошибок контрольных

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

Q Выход блока 16 является одновременно вторым, управляющим выходом устройства. Сигнал 1 на этом выходе формируется, если в принятом кодовом слове ошибочными являются контрольные символы; в про5 тивном случае формируется сигнал О.

Блок селекции ошибок контрольных символов может быть реализован на комбинационных логических схемах, на базе арифметико-логического устройства или

0 ПЗУ. Ниже рассмотрен пример реализации блока 16 на основе ПЗУ. Для представления информации об ошибках контрольных символов в ПЗУ достаточно одного бита на ошибку: 1 может быть использована для

5 кодирования ошибок контрольных символов, а О - для кодирования всех других ошибок. В случае например (31. 26)- кода Хэмминга с порождающим многочленом Y х5+х+1 из 25 - 32 возможных значений

0 синдрома только пять следующих: х+1, х2+Х, х3+х , х4+х3н х4+х+.1 будут являться синдромами ошибок контрольных символов, умно женными на х . Им соответствуют 5-разрядные адреса ПЗУ: 00011, 00110,

5 01100,11000,10011. По этим адресам в ПЗУ надо записать 1, а по остальным - О. Если при чтении содержимого ПЗУ перед коррекцией в качестве источника адреса использовать синдромный регистр, то можно получить информацию о характере ошибки. Если при чтении будет получена 1. то ошибка принадлежит к-контрольным символам. Чтение информации из ПЗУ инициируется сигналом блока управления, поступающим на управляющий вход (вход разрешения обращения) ПЗУ.

Выпускаемые в настоящее время БИС ПЗУ, в частности серии 556 емкостью 1К - 64 К бит в одном корпусе, позволяют созда0

5

вать корректоры ошибок, оперирующие с кодовыми словами любой длины.

Блок управления 17 обеспечивает взаимодействие и синхронизацию работы узлов устройства. Схема блока управления приведена на фиг. 3. Она включает RS-триггеры 12,13,29; генератор тактовых импульсов 15: схемы ИЛИ 16, 24.41, 42; схемы И 17,23, 31, 32, 37, 38; инверторы 18, 33, 35; D-триггеры 26,28; схему ИЛИ-НЕ 27, схемы задержки 39, 40; счетчик тактовых импульсов 44, усилители 14, 25, 30. 34, 36, 43; вход усилителя 14 соединен с входом 19 начальной установки устройства, а выход - со входами сброса триггеров 12, 13, ,26, 28, счетчика тактовых импульсов 44, а также с первым входом схемы ИЛИ 24; вход усилителя 25 соединен с входом 20 сброса ошибки устройства, а выход - с выходом 1 блока управления. Входы установки в 1 триггеров 12, 13 соединены соответственно со входами 21, 22 чтения и коррекции устройства, выход триггера 12 соединен с первыми входами схемы ИЛИ 16 и схем И 23, 38-, а также с выходом 6 блока управления; выход триггера 13 соединен со вторым входом схемы ИЛИ 16 и с первыми входами схем И 17, 37, а также через усилители 30, 36 - с выходами 5, 3 блока управления, выход генератора тактовых импульсов 15 соединен с тактовым входом D-триггера 26 и с первыми входами схем И 31, 32, информационный вход D- триггера 26 соединен с выходом схемы ИЛИ 16, а выход - с вторым входом схемы И 31, третий вход которой соединен с выходом схемы ИЛИ-НЕ 27, выход схемы И 17 соединен с входом инвертора 18 и с первым входом схемы ИЛИ-НЕ 27, выход схемы И 23 соединен с информационным входом D- триггера 28, и с вторыми входами схемы ИЛИ-НЕ 27 и схемы И 32, третий вход которой соединен с выходом D-триггера 28, а выход - с тактовыми входом D-триггера 28, входом инвертора 33 и с выходом 11 блока управления,, выход схемы И 31 соединен со вторыми входами схем И 37, 38 и с входом инвертора 35; второй и третий входы схемы ИЛИ 24 соединены с выходами инверторов 18, 33; входы сброса и установки триггера 29 соединены с выходами схемы ИЛИ 24 и инвертора 35, а выход - через усилитель 34 подключен к выхоДу 10 блока управления и к выходу готовности 23 устройства. Выход схемы И 37 соединен с первым входом схемы ИЛИ 41 и через схему задержки 40 - с первым входом схемы ИЛИ 42; выход схемы И 38 соединен с выходом 8 блока управления и с выходом

5

24 синхронизации источника информации , устройства, а также через схему задержки 39 - со вторым входами схем ИЛИ 41, 42; выход схемы ИЛИ 41 соединен со счетным 5 входом счетчика 44, и с выходом 7 блока управления; выход схемы ИЛИ 42 подключен к выходу 2 блока управления, а также через усилитель 43 - к выходу 9 блока управления и к выходу 25 синхронизации прием0 ника информации устройства; / информационные входы счетчика 44 соединены со вторыми входами схем И 17, 23 и с выходом 4 блока управления.

Блок управления работает следующим

5 образом. Сигналами, поступающими от приемника информации на входы 19, 20, производится сброс синдромного регистра 1 устройства, а также триггеров 12,13, 26,28, 29 и счетчика 44 блока управления. В ре0 зультате этого на выход 10 с выхода триггера 29 через усилитель 34 будет выдаваться сигнал готовности устройства к работе, а на выход 4 - начальный (нулевой) адрес буфера данных 11; на всех других выходах блока управления сигналы будут отсутствовать. В режиме чтения сигнал от приемника информации со входа 21 устанавливает в 1 триггер 12, выходной сигнал которого с выхода

6 переводит буфер данных 11 устройства в режим записи и через схему ИЛИ 16 поступает на информационный вход D-триггера 26. Отрицательный задний фронт первого положительного тактового импульса гене5 ратора 15, накладывающийся на выходной сигнал схемы ИЛИ 16, воздействуя на тактовый вход D-триггера 26, устанавливает его в 1 и разрешает прохождение всех последующих положительных тактовых импуль0 сов генератора 15 через вентиль 31 на входы вентилей 37, 38 и инвертора 35. Первый выходной сигнал инвертора 35 устанавливает в 1 триггер 29, в результате на выходе 10 блока управления и на выходе 23 устрой5 ства снимается сигнал готовности. Проходя через открытый выходным сигналом триггера 12 вентиль 38, тактовые импульсы поступают на выход 8 синхронизации источника информации и через схему задержки 39,

0 схемы ИЛИ 41,42 - на выходы 7, 2, 9 разрешения обращения к буферу данных, сдвига синдромного регистра и синхронизации приемника информации. Инкрементирова- к ние счетчика 44 происходит по заднему фронту сигнала разрешения обращения к буферу данных на выходе 7. После приема кодового слова счетчик 44 будет содержать двоичный код длины п кодового слова. Этот код совместно с выходным сигналом триггеpa 12 обеспечивает срабатывание вентиля 23. Выходной сигнал вентиля 23 через схему ИЛИ-НЕ 27 закрывает вентиль 31, в результате чего прекращается выдача сигналов с выходов 2, 7, 8, 9. Одновременно сигнал с выхода схемы И 23 открывает вентиль 32 и разрешает установку в 1 триггера 28. N+1 - и тактовый импульс генератора 15. проходя через схему И 32, формирует на выходе 11 блока управления сигнал разрешения работы блока селекции ошибок контрольных символов устройства. Этот сигнал через инвертор 33 и схему ИЛИ 24 сбрасывает триггер 29 и включает тем самым на выходе 10 сигнал готовности. По заднему фронту этого же сигнала устанавливается в 1 триггер 28 и закрывает вентиль 32. На этом заканчивается выполнение режима чтения. В режиме коррекции работа блока управления во многом схожа с его работой в режиме чтения. Различие следующее. После начальной установки приемник информации подает сигнал коррекции на вход 22 и устанавливает в 1 триггер 13 блока управления. Выходной сигнал этого триггера через усилители 30,36 формирует на выходах 5, 3 сигналы чтения информации из буфера данных и разрешения работы блока фиксации местоположения ошибки. Выходные сигналы схемы И 31, проходя через открытый выходным сигналом триггера 13 вентиль 37, схему задержки 40, схемы ИЛИ 41, 42 формируют на выходах 7, 2, 9 сигналы обращения к буферу данных, сдвига синдромного регистра и синхронизации приемника информации. После передачи всех п символов кодового слова .срабатывает схема И 17, выходной сигнал которой через схему ИЛИ-НЕ 27 закрывает схему И 31, в результате чего прекращается выдача сигналов с выходов 2,7, 9. Одновременно выходной сигнал схемы И 17 через инвертор 18, схему ИЛИ 24 сбрасывает триггер 29 и на выходе 20 устанавливается сигнал готовности.

Предлагаемое устройство работает следующим образом. Приемник информации проверяет наличие на выходе 23 корректора Ошибок сигнала готовности. Если устройство готово для работы в комплексе с приемником информации, то последний с помощью сигналов, подаваемых на входы 19, 20 перед чтением кодового слова, сбрасывает синдромный регистр 1 и приводит в начальное состояние блок управления 17. Непосредственно чтение кодового слова начинается после поступления на вход 21 от приемника информации сигнала чтения. После этого формируется последовательность

0

5

0

5

0

5

0

5

0

5

сигналов синхронизации, которые с выхода 24 поступают к источнику кодированных сообщений. За одну команду чтения обеспечивается прием и декодирование одного кодового слова. В ответ на каждый синхросигнал источник сообщений передает один символ. Эти символы со входа 18 корректора ошибок без изменений через блок 12 компенсации ошибок поступают на информационный выход 27 и далее- к приемнику информации в сопровождении сигналов синхронизации на выходе 25 устройства. Одновременно принимаемые символы записываются в буфер данных 11 и поступают в блок 5 обратной связи для деления на порождающий многочлен. После приема очередного символа блок управления 17 производит сдвиг вправо на один разряд синдромного регистра 1 и инкрементйрует на 1 код на адресных входах буфера данных 11. Таким образом в процессе последовательного посимвольного деления принятого кодового слова в регистре Т накапливаются частичные остатки от деления всех символов кодового слова, образующие в конечном итоге умножений .на хт синдром ошибки S (УКОД + v0iu). После приема всех символов кодового слова блок управления 17 формирует сигнал разрешения работы блока селекции ошибок контрольных символов 16. По завершении режима чтения устройство выдает на выход 23 сигнал готовности, на выход 26 - сигнал о наличии или отсутствии ошибок в принятом кодовом слове и на выход 28 - сигнал о наличии или отсутствии среди обнаруженных ошибок, ошибок контрольных символов. После анализа вышеперечисленны/ сигналов приемник информации может осуществить чтение следующего кодового слова, если не было обнаружено ошибок 3 приема или если обнаруженные ошибки относятся к контрольным символам. Если же искажению подверглись информационные символы, то необходима коррекция ошибок. Перед началом коррекции приемник информации подает сигнал на вход 19 и при- водит блок управления в начальное состояние; при этом сигная сброса ошибки на вход 20 не подаётся, с тем, чтобы сохранить синдром ошибки для ее исправления. Непосредственное осуществление коррекции начинается прсле /йШэчи на вход 22 приемником информации, ьёйгнала коррекции При этом блок управления 17 разрешает работу блока фиксацииместоположения ошибки 10, формирует сигналы чтения со- ржимого буфера данных 11. сдвига синдромного регистра 1, инкрементирует код на адресных входах буфера данных 11. Считываемое из буфера данных 11 ранее принятое кодовое слово посимвольно передается через блок компенсации ошибки 12, на выход 27 устройства и далее к приемнику информации. Выдаваемые символы сопровождаются сигналами синхронизации на выходе 25 устройства. Одновременно с выдачей очередного символа сдвигается на один разряд синдромный регистр 1 для умножения на х содержащего в нем синдрома ошибки. После того, как в процессе последовательного умножения синдрома будет сформирован вектор ошибки, блок 10 вырабатывает сигнал, Который поступит на вход коррекции блока 5 и разорвет обратную связь синдромного регистра 1. Этот же сигнал поступит на вход коррекции блока компенсации ошибки 12 и разрешит передачу вектора ошибки с управляющего выхода синдромного регистра 1 в блок 12 компен сации ошибки. Блок 12 исправляет поступающее в него из буфера данных 11 искаженное кодовое слово и выдает его на выход 27 устройства. Исправленное информационное слово с выхода 27 и сопровождающие его сигналы синхронизации с выхода 25 корректора ошибок поступают к приемнику информации. После окончания передачи исправленного сообщения корректор ошибок вырабатывает сигнал готовности и выдает его на выход 23.

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

Для иллюстрации рассмотрим циклический (n°, k, m).- код, например код Хэммингз (7,4, 3), (15,11,4), (31, 26, 5). Здесь п -длина кодового слова, k - длина информационного поля, m n - k - количество контрольных символов. При равновероятном распределении вероятность расположения ошибки в поле контрольных символов для трех выше- .указанных кодов Хэмминга составит соответственно 0,43; 0,27; 0,16. Таким образом предлагаемое устройство позволит увеличить быстродействие при коррекции соответственно на 43%, 27%, 16%.

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

Корректор ошибок, содержащий регистр синдрома, блок обратной связи, детектор ошибки, блок . фиксации

0

5

0

5

0

5

0

5

0

5

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

И

мшг

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