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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК А 03 М 13/02 ПИСАНИЕ ИЗОБРЕТЕНА ВТОРСКОМУ СВИДЕТЕЛЬСТВУ ий енко,ССС 80, СР етельство 1. 1/10, 1 ельство С 1, 1/10, 1 ИСПРАВЛЕ ОШ зоватьтной ин передачи дискре спечивает повышУстройство со га, сумматор 2 ик ошибок 3, сч ормирователь 5 ной последовате форм ии и обе ействия 1 сдви и ерж о м ст еги дулю два, да 4 импульсов, ма информаци преобразоват индроьности локи и кодов 6 и Фиг. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(57) Изобретение может испося в системах,ЯО 327297 памяти 8 и 12, блок элементов ИЛИ 9, формирователь 10 проверочной последовательности и управляющий блок 11,. Принимаемая и-разрядная кодовая комбинация поступает в регистр 1 сдвигаормирователь 5. Синдром вычисляется поразрядным сложением по модулю два строк проверочной матрицы, .соответствующих единицам в принятой кодовой комбинации. С помощью счетчика 9 и формирователя 10 устанавливается . двоичная комбинация соответствующей строки проверочной матрицы. При отсутствии ошибок синдром равен нулю и принятая комбинация с регистра 1 без изменений проходит на выход уст- аЮ ройства. При одиночной ошибке в -й позиции синдром представляет собой строку проверочной матрицы, номер которой равен д. Исправление проис- . С ходит инвертированием, Поясняется вьг явление и исправление двух и более ошибок. 5 ил. 3 авй30 50 1 13272Изобретение относится к электросвязи и может быть использовано в системах передачи дискретной информациидля защиты от ошибок принимаемой информации.Цель изобретения - повышение быстродействия.На фиг.1 представлена структурнаяэлектрическая схема устройства для исО правления ошибок; на фиг.2 - структурная электрическая схема датчика ошибок; на фиг.3 - формирователь синдрома информационной последовательности; на фиг.4 - первый блок памяти; 5 на фиг.5 - управляющий блок.Устройство для исправления ошибок содержит регистр 1 сдвига, сумматор 2 по модулю два, датчик 3 ошибок, счетчик 4 импульсов, формирователь 5 синдрома информационной последовательности, первый и второй преобразователи 6 и 7 кодов, первый блок 8 памяти, блок 9 элементов ИЛИ, формирователь10 проверочкой последовательности, 25 управляющий блок 11, второй блок 12 памяти.Датчик 3 ошибок содержит счетчик13 импульсов, блок 14 счетчиков им-. пульсов и элемент ИЛИ 15.формирователь 5 синдрома информационной последовательности содержит блок 16 элементов И, элемент ИЛИ 17 и блок 18 Р-триггеров.Первый блок 8 памяти содержит счетчик 19 импульсов, дешифраторы 20- 22, блок 23 адресных регистров, блок 24 шинных формирователей, постоянный запоминающий блок 25, дешифратор 26,Управляющий блок 11 содержит КЯ- триггер 27, элемент И 28, инвертор 29, элемент И 30, элемент ИЛИ 31, счетчик 32 микрокоманд, постоянный запоминающий блок 33 микрокоманд, регистр 34 микрокоманд, дешифратор 45 35 управляющих сигналов, генератор 36 тактовых импульсов, элементы И 37 и 38, КБ-триггер 39.Устройство для исправления ошибок работает следующим образом.Принимаемая и-разрядная кодовая комбинация (входной сигнал) поэлементно поступает в регистр 1 и формирователь 5 (фиг.1). Синдром вычисляется поразрядным сложением по моду лю два строк проверочной матрицы, соответствующих единицам в принятой кодовой комбинации, При этом двоичный номер анализируемого элемента при 97. 2нятой комбинации с выходов разрядовсчетчика 4 через блок 9 элементов ИЛИподается на вход Формирователя 1 О, навыходе которого устанавливается исразрядная двоичная комбинация соот-,ветствующей строки проверочной матрицы. По окончании приема кодовой комбинации в счетчике 4 вырабатываетсясигнал окончания вычисления синдромов,который поступает в управляющий блок11.В случае отсутствия ошибок синдром равен нулю. При этом в управляющий блок 11 с первого преобразователя6 кодов не поступает никаких сигналов, Управляющий блок 11 остается висходном состоянии. Принятая комбинация с выхода регистра 1 без измененийпоступает на выход устройства для исправления ошибок,Для случая одиночной ошибки в д-йпозиции синдром представляет собойстроку проверочной матрицы, комер которой равенОперация сравнения синдрома состроками проверочной матрицы осуществляется первым преобразователем 6кодов, с выхоца "Номер строки проверочной матрицы которого в случае ихсовпадения в датчик 3 ошибок поступает двоичный 1-разрядный код числа, Вдатчике 3 ошибок формируется Е-разрядный вектор ошибки, в котором всепозиции, кроме д-й, равны нулю. Вектор ошибки в сумматоре 2 поэлементноскладывается по модулю два с информационной частью кодовой комбинации свыхода регистра 1. При этом происходит инвертирование 1-го элемента,т,е. исправление ошибки. Исправленная комбинация далее поступает на выход устройства для исправления ошибок.Если произошло две ошибки, то синдром не совпадает ни с одной иэ строкпроверочной матрицы. Это отличие устанавливается первым преобразователем6 кодов, который при появлении запрещенной комбинации на входах формируетсигнал несовпадения поступающий вуправляющий блок 11. На выходах второго преобразователя 7 кодов появляется двоичный код номера крайней правой, отличной от нуля, позиции синдрома, поступающий в первый блок 8 памяти. На информационных выходах первого блока 8 памяти появляется 1-разрядный двоичный код номера одной изстрок транспонированной проверочнойматрицы, содержащей единицу в позиции,номер которой определен в блоке 7,Этот код сигналом 11 Вычисление" с вы 11 15хода Вычисление управляющего блока11 записывается во второй блок 12 памяти и одновременно через блок 9 элементов ИЛИ поступает на вход формирователя О. При этом на его выходахустанавливается и-Е-разрядная двоичная комбинация, соответствующая данной строке проверочной матрицы, которая подается в формирователь 5.Одновременно в формирователе 5 по 15сигналу 1 Вычисление 11 происходит сло -жение по модулю два выбранной строкипроверочной матрицы с ранее вычисленным синдромом. Полученный при этомпервый модифицированный синдром поступает на вход первого преобразователя 6 кодов, который, в случае совпадения модифицированного синдрома содной из строк проверочной матрицы,формирует на выходе "Номер строки 25проверочной матрицы" 1-разрядный двоичный код номера этой строки. Этоткод записывается в датчик 3 ошибок.Затем по сигналу "Вывод" с выхода 1 Вывод" управляющего блока 11, из второго блока 12 памяти, выполненного ввиде блока стековой памяти, считывается в 1-разрядный код номера строкиматрицы, участвовавшей в вычислениимодифицированного синдрома, являющийся в данном случае кодом номера другой искаженной позиции, и записывается в датчик 3 ошибок, в которомформируется вектор ошибки, представляющей собой 1-разрядную двоичную 40комбинацию с единицами в тех разрядах, номера которых заданы поступившими в датчик 3 ошибок командами,Формирование вектора ошибки и исправление ошибок происходит так же, 45как и в случае одиночной ошибки,Если модифицированный синдром .несовпадает ни с одной из строк проверочной матрицы на управляющий блок11 с первого преобразователя 6 кодовпоступает сигнал несовпадения. В управляющем блоке 11 вырабатываетсясигнал "Вычисление", по которому сранее выбранной страницы первого блока 8 памяти считывается 1-разрядныйдвоичный код номера следующей строкиматрицы, содержащей единицу в соответствующем разряде, Этот номер также запоминается во втором блоке 12 памяти вместо ранее записанного. Затем, в соответствии с поступившим из первого блока 8 памяти через блок 9 элементов ИЛИ кодом, формирователем 5 считывается и-разрядная двоичная комбинация строки проверочной матрицы и происходит вычисление нового модифицированного синдрома. Такая процедура вычисления модифицированного синдрома продолжается до его совпадения с одной из строк проверочной матрицы. После этого в соответствии с указанной процедурой, происходит исправление ошибок.Если ни один иэ модифицированных синдромов не совпадает со строками проверочной матрицы, значит произошло более двух ошибок. В первом блоке 8 памяти на выходе "Конец страницы" формируется сигнал конца страницы, который поступает в управляющий блок 11. Тогда для каждого первого модифицированного синдрома указанным образом в формирователе 5 происходит вычисление вторых модифицированных синдромов.Если ни один из вторых модифицированных синдромов не совпадает со строками проверочной матрицы, то для каждого второго модифицированного синдрома вычисляется третий и т.д. Процедура вычисления модифицированных синдромов продолжается до тех пор, пока какои-либо иэ Б-х модифицированных синдромов не совпадает с одной из строк проверочной матрицы (Б - количество ошибок в комбинации) либо пока не будут исследованы все возможные -1-вые синдромы (С - кратность исправления ошибок данным кодом).Совпадение фиксируется в первом преобразователе 6 кодов, который формирует 1-разрядный двоичный код номера соответствующей строки проверочной матрицы, являющийся номером позиции одной из ошибок в принятой комбинации, При этом во втором блоке 12 памяти записаны сигналом Вычисление11 11 коды номеров строк проверочной матрицы, участвовавших в вычислении моди- . фицированных синдромов на всех этапах вычислений, которые будут,совпадать с номерами позиций остальных 8-1 ошибок в принятой комбинации. По сигналу "Вывод" управляющего блока 11 коды номеров позиций ошибок с первого преобразователя 6 кодов и вто1327297 рого блока 12 памяти, поступают в датчик 3 ошибок, в котором формируется вектор ошибки, представляющий собой 1-разрядную двоичную комбинацию, с единицами в тех разРядах, номеРа 5 которых заданы поступившими в датчик ошибок кодами. Происходит исправление ошибок путем поразрядного сложения по модулю два в сумматоре 2 вектора ошибки и информационной части принятой 10 кодовой комбинации с выхода регистра 1.Датчик 3 ошибок (фиг.2) работает следующим образом.1-Разрядный код позиции ошибки с входа",Номер строки проверочной матрицы" инвертированным сигналом "Несовпадение записывается в счетчик 13. Далее 1-разрядный код позиции ошибки информационных входов записы вается по сигналу Вывод" в первый счетчик блока 14 счетчиков, на выходах которого устанавливается записанный код. По следующему сигналу "Вывод" этот код переписывается во второй счетчик, а 1-разрядный код позиции ошибки записывается в первый счетчик и т.д. Далее по тактовым импульсам соответствующие счетчики начинают отсчет, В те моменты, когда количество отсчитанных тактовых импульсов совпадает с номером позиции ошибки, ранее записанном в каком-либо из счетчиков, на выходе (Оя этого счетчика появляется сигнал, который 35 через элемент ИЛИ 15 поступает на выход.Формирователь 5 (фиг.3) работает следующим образом.и-разрядный двоичный код, соот ветствующий соответствующей строке проверочной матрицы, поразрядно поступает на первые входы элементов И блока элементов, на вторые входы которых поступает сигнал с выхода эле мента ИЛИ 17. На входы последнего подаются сигналы Информация" и "Вычисление . Причем, первый из них используется при вычислении основного синдрома, а второй - при вычислении 0 модифицированных синдромов. При наличии единичного сигнала на выходе элемента ИЛИ 17 элементы И блока 1 б Нулевое состояние счетчика 19 вызывает установку единичного потенциала на первом выходе дешифратора 22,разрешающего работу первого шинногоформирователя блока 24 шинных формирователей, который подключает к адресному входу постоянного запоминающего блока (ПЗБ) 25 выход первого адресного регистра блока 23 адресныхрегистров. При этом разрешается обращение к той области памяти ПЗБ 25, вкоторой хранятся номера строк проверочной матрицы, содержащих единицув определенной позиции. Для этого,при программировании ПЗБ 25 весь объем памяти разделен на страницы" объемом и/2 1-разрядных слов так, чтов первой "странице" хранятся номерастрок матрицы, содержащих единицу впервой позиции, во второй "странице"номера строк, содержащих единицу вовторой позиции и т.д,элементов открываются и сигналы с ихвыходов подаются на входы соответствующих П-триггеров блока 18,П-триггеры, на входы которых вданный момент поступили единицы, изменяют свое состояние, так как оивключены в счетном режиме. При вычислении синдромов осуществляется счетчисла единиц по каждому разряду синдрома. Если это число - четное, то соответствующий 0-триггер очищается, аесли нечетное - устанавливается. Таким образом, блок 18 0-триггеров выполняет функции накапливающего поразрядного сумматора по модулю два. Сигналом "Сброс" с блока 11 производится начальная очистка накапливающегопоразрядного сумматора по модулю два,перед вычислением очередного основного синдрома.Первый блок 8 памяти (фиг.4) перед приемом очередной кодовой комбинации устанавливается в исходное состояние. Для этого импульсом Сброс"очищается счетчик 19. Адресные регистры блока 23 адресных регистров могут быть в произвольном состоянии.После установки на информационныхвходах номера позиции крайней правойединицы в синдроме поступает сигналЗапись" (последовательность операции задается управляющим блоком 11),Так как счетчик 19 находится в нулевом состоянии, то сигналЗапись" вызывает появление сигнала на первомвыходе дешифратора 20. Этим сигналомпроизводится запись кода номера позиции крайней правой единицы в первый регистр блока 23 адресных регистров, 7 1327Сигнал "Счет", поступающий в блок 8 памяти, вызывает появление на первом выходе дешифратора 21 сигнала, который поступает на счетный вход счетчика первого адресного регистра блока 23 адресных регистров. При этом его содержимое увеличивается на единицу и осуществляется обращение к следующей ячейке выбранной страницы, 10 Затем поступает очередной сигнал Счет и т.д. В этом случае на выходе дешифратора 26 появляется сигнал "Конец страницы".По сигналу Выбор адреса (+ 1 ) 15 увеличивается на единицу содержимое счетчика 19. При этом единичным потенциалом с второго выхода дешифратора 22 разрешается работа второго шинного формирователя блока 24 шин ных формирователей, т.е. к адресному входу ПЗБ подключается выход второго адресного регистра блока 23 адресных регистров.Сигнал "Запись" вызывает появление 25 сигнала на втором выходе дешифратора 20, т.е. на входе "Запись" второго адресного регистра блока 23 адресных регистров. Аналогично, сигнал "Счет" преобразуется в сигнал на втором вы ходе дешифратора 21, т,е. на счетном входе второго адресного регистра блока 23 адресных регистров.Появление сигнала "Выбор адреса" ("-") вызывает уменьшение содержимо- З 5 го счетчика 19 на единицу. Управляющий блок 11 (фиг,5) работает по принципу микропрограммного управления. В узле пуска, состоящем из элементов И 37 и 38 и Ю-триггера 39, в исходном 40 состоянии (перед приемом очередной кодовой комбинации) КБ-триггер 39 очи. щен сигналом "Сброс", Сигналом "Конец вычисления", при условии единичного сигнала Несовпадение", КБ-триггер 45 39 устанавливается в состояние "1". При этом открывается элемент И 37. Сигналы сенератора 36 начинают поступать в счетчик 32, регистр 34 и дешифратор 35.50Узел выбора адреса следующей микрокоманды состоит из КБ-триггера 27, элементов И 28 и 30, инвертора 29, элемента ИЛИ 31 и счетчика 32. При появлении безусловных команд содержимое счетчика 32 (адрес микрокоманды) наращивается на единицу по сигналу с выхода элемента И 37. В случае условной команды возможны два ва 297рианта: переход к следующей микрокоманде (наращивание содержимого счетчика 32 на единицу), если некоторое условие не выполняется, или переход по адресу из регистра 34 (загрузка в счетчик 32 адреса новой микрокоманды из регистра 34),если это условие выполнено. В данном случае условием, вызывающим переход на новый адрес, является отсутствие сигналов "Несовпадение" и "Конец страницы".КБ-триггер 27 служит для фиксации сигнала "Конец страницы". Его основное состояние "1" на выходе, установленная сигналом Запись . При выполнении команды Переход по условию конец страницы вырабатывается управляющий сигнал "Условие 1", который поступает на первый вход элемента И 28, на второй вход которого подан единичный потенциал с выхода КЯ-триггера 27.Единичный сигнал с выхода открытого элемента И 28 поступает через элемент ИЛИ 31 на вход предварительной установки счетчика 32. При этом происходит запись в счетчик 32 адреса новой микрокоманды из регистра 34. Сигналом Конец страницы" КЯ-триггер 27 очищается, Элемент И 28 запирается и при выполнении условной команды сигнал "Условие 1" не проходит на вход предварительной установки счетчика 32. В этом случае содержимое счетчика 32 наращивается на единицу сигналом с выхода элемента И 37, т.е. происходит переход к следующей микрокоманде.При выполнении микрокоманды Переход по условию совпадение" вырабатывается управляющий сигнал нусловие 2", поступающий на первый вход элемента И 30, на второй вход которого поступает сигнал Совпадение с выхода инвертора 29, являющийся инвертированным сигналом Несовпадение". Если сигнал "Совпадение" единичный, то элемент И 30 открыт и сигнал "Условие 2" проходит с его выхода через элемент ИЛИ 31 на вход предварительной записи счетчика 32, Происходит переход на новую микрокоманду по адресу из регистра 34. Если сигнал "Совпадение" - нулевой, то элемент И 30 заперт и условного перехода не происходит. В эТом случае выполняется следующая микрокоманда, т.е. содержимое счетчика 32 наращивается на единицу.Выполнение каждой микрокоманды начинается с записи кода микрокоманды в регистр 34. При этом адрес микро- команды с выхода счетчика 32 поступа 5 ет на вход постоянного запоминающего блока 33, на выходе которого устанавливается код микрокоманды. Далее по сигналу с выхода элемента И 37 этот код записывается в регистр 34. Выходы первых разрядов регистра 34 подключены к соответствующим входам дешифратора 35, который в соответствии с кодом, поступившим на его входы, формирует на одном из своих вйходов управляющий сигнал. Вторые выходы регистра 34 подключены к информационным входам счетчика 32 и,служат для записи в счетчик 32 адреса следующей микрокоманды при условии перехода,Формула изобретенияУстройство для исправления ошибок, 25 содержащее последовательно соединенные датчик ошибок и сумматор по модулю два, а также регистр сдвига и Формирователь проверочной последовательности, причем информационный вход регистра сдвига и объединенный тактовый вход регистра сдвига и датчика ошибок являются соответственно информационным и тактовым входами устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, введены последовательно соединенные счетчик импульсов, управляющий блок и первый блок памяти, а также блок элементов ИЛИ, формирователь синдрома инО формационной последовательности, первый и второй преобразователи кодов и второй блок памяти, при этом тактовый вход счетчика импульсов подключен к тактовому входу регистра сдвига, выход которого подсоединен к второму входу сумматора по модулю два, информационный вход и входы проверочной последовательности формирователя синдрома информационной последовательносО ти подключены соответственно к информационному входу регистра сдвига и оответствующим выходам формирователя проверочной последовательности, вход которого подключен к выходу блока элементов ИЛИ, вход сигнала ЯВычисление" формирователя синдрома информационной послецовательности объединен с входом сигнала Вычисление" второго блока памяти и подключен к выходу сигнала "Вычисление" управляющего блока, выходы разрядов счетчика импульсов подсоединены к первым входам блока элементов ИЛИ, вторые входы которого объединены с информационными входами второго блока памяти и подключены к соответствующим информационным выходам первого блока памяти, третьи входы блока элементов ИЛИ объединены с информационными входами датчика ошибок и подсоединены к соответствующим выходам второго блока памяти, вход "Вывод информации" которого объединен с входом "Вывод информации датчика ошибок и подключен к выходу "Вывод информации управляющего блока, выход "Сброс которого подсоединен к входам "Сброспервого и второго блоков памяти, счетчика импульсов и формирователя синдрома информационной последовательности, выходы которого подсоединены через первый преобразователь кодов к соответствующим входам "Номер строки проверочной матрицы" датчика ошибок, а через второй преобразователь кодов - к соответствующим информационным входам первого блока памяти, входы сигналов "Запись "Счет" и "Выбор адреса" которогоподключены состветственно к выходам сигналов Запись, Счет и второму выходу сигнала "Выбор адреса" управляющего блока, вход сигнала "Конец страницы которого подключен к выходу сигнала "Конец страницы" первого блока памяти, а вход сигнала "Несовпадение" управляющего блока объединен с входом сигнала "Несовпадение" датчика ошибок и подключен к дополнительному выходу первого преобразователя кодов, причем выход сумматора по модулю два является выходом устройства.1327297 вяоа.йвдеФ иг. Ф йгю аиа ЧИЖ оставительехред Л.Сер актор И,Касарда каз 3399 ВНИИПИ Го венног обретении Ж, Р