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

(51)5 Н 03 И 13/00 госудАРственный комитетПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР Я; ОПИСАНИЕ ИЗОБРЕТ ТЕЛЬСТВ ВТОРСКОМУ СВИ Р 13С.И. Иванов етельство СС М 1/00, 198 блок 3(54) УСТРОРСТВО ДЛЯПРАВЛЕНИЯ ОП 1 ИБОК(57) Изобретение опередачи данных и АРУЖЕНИЯ носится к техножет быть испол з,.801640814 А 1 вано в системах передачи дискретноиинФормации по каналам низкого качества для исправления ошибок при многократном повторении сообщений. 1 елью изобретения является повышениебыстродействия и достоверности устройства. Устройство содержит блок 1коммутации, элементы И 2 и 6,исправления ошибок, блок 4 управления, элемент НЕ 5, регистры 7 и 10сдвига, сумматор 8 по модулю два,элемент ИЛИ 9., 2 з,п, ф-лы, 3 ил.го Изобретение относится к техникепередачи данных и может быть использовано в системах передачи дискретнойинформации по каналам низкого качества для исправления ошибок при многократном повторении сообщений.11 елью изобретения является повышение быстродействия и достоверностиустройства,На фиг. 1 представлена функциональная схема устройства; на фиг, 2 -функциональная схема блока исправления ошибок; на фиг. 3 - функциональная схема блока управления.15Устройство содержит блок 1 коммутации, элемент И 2, блок 3 исправления ошибок, блок 4 управления,элемент НЕ. 5, элемент И 6, регистр 7сдвига, сумматор 8 по модулю два,элемент ИЛИ 9, регистр 10 сдвига.20Блок 3 содержит элемент ИЛИ 11,регистр 12 сдвига, коммутатор 13,элементИЛИ 14 регистр 15 сдвига, счетчик 16 импульсов элемент И 17 дшфрр 18 суммтор 19,регистр 20 сдвига, группу 21 ключей,Сумматор 19 предназначен для формирования двоичного кода числа п+1,,где щ - число единиц в предполагаемомсиндроме ошибок,30Дешифратор 18 предназначен дляформирования двоичного числа 2,которое определяет коэффициент переполнения счетчика 16Счетчик 16 импульсов предназначендля формирования одной из 2 щ двоичных комбинаций, которые используютсяпри переборе различных вариантов кодовой комбинации.Елок 4 управления содержит элемент,22 И, умножитель 23 частоты, генератор 24 тактовых импульсов, триггер 25коммутатор 26, счетчик 27 импульсов,триггер 28,счетчики 29 и 30 импульсов.Генератор 24 тактовых импульсов 45предназначен для формирования тактовыхимпульсов с частотой К , соответствующей тактовой частоте поступления вустройство информационных символов.Умножитель 23 частоты предназначен для формирования тактовых импульсов с частотой Гт = 1 с Г , на.которой1осуществляется работа.Устройство реализует следующийметод исправления ошибок. Исправление ошибок начинается после передачи55второго повтора кодовой комбинации(КК), Сначала осуществляется пораз"рядное сравнение первого и второго повторов КК и формирование предполагаемого синдрома ошибок (ПСО) разрядностью и, в котором "О" соответствует совпадению символов одноименныхраэрядов первого и второго повторовКК, а "1" - несовпадению, Затем производится полный перебор (.2 комбйнаций, ш - количество единиц в ПСО) возможных вариантов КК, поочередно подставляя на позиции КК, помеченные"единицей" в ПСО одну из 2 комбинаций "0" и "1", Например,1 0 0 0 1 0 1 О 1 1 0 - первый повторКК1 0 1 01001 1 10 - второйповторКК0 0 1 0 0 0 1 1 0 0 0 - ПСО10001000110.10001001110100010101101 0 0 0 1 0 1 1 1 1 0 возможныеооооо101010011101010101011010101011110При этом каждый вариант КК проверяется на наличие ошибок Если послеперебора всех вариантов КК ошибки исправлены не будут, то осуществляетсяприем третьего повтора КК, формирование очередного ПСО с учетом трех повторов и перебор возможных вариантовКК с проверкой их на наличие ошибок,Если после этого ошибки исправленыне будут, осуществляется прием 4-гоповтора КК и т.д. Из сказанного сле 1дует, что при М-м повторе КК ошибки .не будут исправлены в том случае, еслихотя бы в одной позиции КК во всехМ-повторах присутствует ошибочный символ, т.е, вероятность декодирования наМ повторе КК равна.= ( -1 ф)"Дм 0Устройство работает следующим образом,.При поступлении первого повтора кодовой комбинации (КК) на информационный вход устройства на вход "Началоприема" подается единичный импульс, всоответствии с которым единичный сигнал с выхода блока 4 управления коимутирует выход блока 1 коммутации сего первым входом и открывает элементИ 2, Кроме того, по сигналу "Началоприема" с пятого выхода блока 4 управления начинают поступать тактовые импульсы, Первый повтор КК через элемент55 5 16408 И 2 поступает на первый вход блока 3 исправления ошибок и записывается в него, а также, под воздействием импульсов сдвига, действующих на вход регистра 7 сдвига, записывается в него. Кроме того, первый повтор КК через блок 1 коммутации поступает на выход устройства для проверки на наличие ошибок.Если в КК будут обнаружены ошиб 10 ки, то осуществляется прием следующего повтора КК. При этом на первом выходе блока 4 управления действует нулевой сигнал, в соответствии с ко 15 торым блок 1 коммутации коммутирует выход с третьим входом. Этот же сигнал закрывает элемент И 2 и через элемент НЕ 5 открывает элемент И 6,Второй повтор КК под воздействием 20 импульсов сдвига записывается в первый регистр 7 сдвига,а также поступает через второй элемент И на второй вход сумматора 8 по модулю "2", где поразрядно суммируется с первым повтором КК, поступающим на его первый вход из регистра 7 сдвига. Результат сложения первого и второго повторов КК через элемент ИЛИ 9 под воздействием импульсов сдвига, поступающих на второй вход второго регистра 10 сдвига записывается в этот регистр, Таким образом, в регистре 10 сдвига записывается двоичная последовательность, в которой Э соответствует совпадению символов одноименных разрядов первого и второго повторов КК, а "1" - их несовпадению, т.е. единицами помечаются "ненадежные" символы, в которых с наибольшей вероятностью могут быть ошибки (в дальнейшем. будем называть эту последовательность предполагаемым синдромом ошибок - ПСО.После окончания приема второго повтора КК со второго и третьего выходов блока 4 управления на соответствующие входы блока 3 исправления ошибок поступают единичные импульсы, а с четвертого выхода блока 4 управления на четвертый вход блока 3 исправления ошибок начинают поступать тактовые импульсы с частотой Г-, = = 1 с Ю , где Ет - тактовая частота приема КК: К 10 - 10 (увеличениефтактовой частоты для обработки КК в блоке 3 исправления ошибок обусловлено необходимостью реализации процедуры исправления ошибок в реальном 146масштабе времени), Одновременно с этим из регистра 10 сдвига на третьи входы блока 3 исправления ошибок поступает в параллельном коде ПСО. После этого в блоке 3 исправления ошибок осуществляется перебор вариантов КК в соответствии с изложенным вьппе алгоритмом, При этом каждый вариант КК с выхода блока 3 исправления ошибок через блок 1 коммутации поступает на выход устройства, где он проверяется на наличие ошибок,В случае, если после приема второго повтора КК ошибки исправлены не будут, то осуществляется исправление ошибок с использованием третьего повтора КК . При этом второй ПСОформируется следующим образом. В сумматоре 8 по модулю два осуществляется поразрядное сложение второго повтора КК, поступающего из регистра 7 сдвига, и третьего повтора КК, поступающего через элемент И 6, Одновременно с этим третий повтор КК под действием импульсов записи записывается в регистр 7 сдвига, Результат сложения по модулю два второго и третьего пдвторов КК поступает на первьп вход элемента ИЛИ 9 на второй вход которого синхронно поступает ПСО 1 с второго выхода регистра 10 сдвига (под воздействием импульсов сдвига выхода блока 4 управления), Таким образом, в регистр 10 сдвига записывается очередной ПСО, учитывающий первьп, второй и третий.повторы КК. Палее осуществляется исправление ошибок аналогично описанной выше процедуре,Если при этом ошибки исправленыне будут, то осуществляется приемчетвертого повтора КК, формированиеПСО, исправление ошибок и т.д,В случае полного исправления ошибок на вход "Конец приема" устройстваподается единичный сигнал, которыйсбрасывает в исходное .состояние регистры 7 и 10 сдвига и элементы блока3 исправления ошибок и блока 4 управления. Устройство готово к следующему циклу работы.Блок 3 исправления ошибок работаетследующим образом.В исходном состоянии счетчик 16,регистры 12 15 и 20 сдвига находятЭся в сброшенном состоянии, Первыйповтор КК,.поступающий на первьп входблока исйравления ошибок, записывдет 1640814ся через элемент ИЛИ 11 в регистр 12сдвига под воздействием импульсовсдвига, поступающих на его пятыйвход из блока 4 управления. Процедура 5исправления ошибок после первого повтора не осуществляется, После приема второго повтора КК сформированныйПС 0,1 в параллельном коде поступаетчерез пятый вход блока 3 исправления 1 Оошибок на вторые входы группы 21 ключей, на вход которого из блока 4управления через четвертый вход блока3 исправления ошибок поступает единичный импульс, разрешающий прохождение ПСО 1 на входы сумматора 19 ичетвертые входы регистра 20 сдвига,куда последний и записывается, В сумматоре 19 осуществляется сложениесимволов ПСО и прибавление к ним 20единицы,т,е, на выходы сумматора 19действует двоичный код, соответствующий количеству единиц в ПСО, увеличенное на единицу (в+1),В соответствии с этим кодом, поступающим на входы деширатора 18на (ш+1) выходе его действует единичный сигнал, что соответствует двоичному коду числа 2. Двоичный код этого числа поступает на вторые входы 30счетчика 16 и воспринимается им каккоэффициенты переполнения, На первыйвход счетчика 16 поступают единичныеимпульсы с периодом и 1 т, под воздействием которых счетчик последовательно принимает одно из 2 состояний, которые записываются в регистр15 сдвига,Одновременно с этим на третьи входы регистров 12 и 20 сдвига начинаютпоступать с первого входа блока 3исправления ошибок импульсы сдвига,под воздействием которых из этих регистров осуществляется последовательное. считывание записанных в них комбинаций на первый и третий вход коммутатора 13 соответственно. Третийвход коммутатора 13 является управляюпдм: при воздействии на него "1."импульс сдвига проходит через открывшийся элемент И 17 на третий вход(сдвига) регистра 15 сдвига и подего воздействием на выход этого регистра считывается содержимое егопервого разряда которое через комму 155татор 13. поступает на выход блокаисправления ошибок; при воздействии"0" элемент И 17 закрывается, не пропуская импульс сдвига на третий вход регистра 15, а содержимое первогоразряда регистра 12 сдвига через коммутатор 13 считывается на выход блока3 исправления ошибок. Под воздействиемимпульсов сдвига, поступающих на третьи входы регистров 12 и 20 сдвига,при считывании содержимого из первогоразряда осуществляется запись этогосимвола в их последний разряд., Такимобразом, по окончании полного считывания регистры содержат исходную комбинациюПри считывании через коммутатор13 на выход блока 3 исправленияошибок символов КК, если ошибки полностью не будут исправлены,на четвертый вход блока исправления ошибокпоступает единичный импульс, подвоздействием которого счетчик 16 принимает свое очередное состояние иосуществляется следующий цикл работыблока исправления ошибок по алгоритму,идентичному описанному выше и т.д.Если при полном переборе 2 возможЩных КК ошибки исправлены не будут,осуществляется исправление ошибокс использованием следующего повтораКК, На четвертый вход блока 3 исправления ошибок поступает единичный импульс, который через элемент ИЛИ 14сбрасывает в исходное состояние регистр15 сдвига и разрешает прохождениеочередного ПСО, поступающего натретьи входы блока исправления.ошибок, на выходы группы 21 ключей,Далее работа блока исправленияошибок осуществляется также как ипри исправлении ошибок с предыдущимповтором КК,При поступлении на шестой входблока 3 исправления ошибок единичногоимпульса "Конец приема этот импульспоступает на вторые входы регистров12 и 20 сдвига и через элемент ИЛИ 14 -на второй вход регистра 15 сдвига,а также на третий вход счетчика 16.Под воздействием этого импульса регистры 12, 15 и 20 сдвига и счетчик16 сбрасываются в исходное состояние.Блок управления работает следующим образом.В исходном состоянии счетчики 27, 29,30 сброшены, триггеры 25 и 28 находятся в нулевом состоянии,При поступлении на второй входблока 4 управления импульса "Началоприема" триггеры 25 и 28 переходятв единичное состояние, Сигнал единич 1640814ного уровня с выхода триггера 28 поступает на первый выход блока 4 управления, а сигнал единичного уровняс выхода триггера 25 запускает генератор 24 тактовых импульсов, который5начинает Формировать импульс с такто"вой частотой, равной частоте поступления символов КК на вход устройства.Тактовые импульсы (ТИ) поступают начетвертьП 1 выход блока 4 управления,а также на вход умножителя 23 частоты,на выходе которого действуют ТИ счастотой в К раз больше, чем на выходе (К л 10 Э - 10 ) Кроме того, 15ТИ с выхода генератора 23 тактовыхимпульсов поступают на первьп входсчетчика 30, коэАЬициент переполнения которого равен и (и - разрядность КК) и на первьп вход коммутатора 26, который в зависимости отсигнала, действующего на его третийвход, соединяет свой выход с первымили вторым входом: при "1" - с вторым входом; при "0" - с первым.25Так как в исходном состоянии счетчик 29 сброшен, то на третьем входекоммутатора 26 действует сигнал нулевого уровня, в соответствии с которым на его выход поступают сигналы с 30первого входа.Импульсы от генератора 24 тактовых импульсов через коммутатор 26поступают на первый вход (счетный)счетчика 27, коэффициент переполнения которого равен и, При поступлении и-го импульса на первый входсчетчика 27 он переполняется и на еговыходе появляется импульс, которьп 1поступает на второй выход блока 4 40управления, на второй вход триггера28, переводя его в нулевое состояние (на первом выходе блока 4 управления действует сигнал нулевого уровня) и на первый вход счетчика 29, 45коэффициент переполнения которогоравен двум, Этот же импульс сбрасывает в исходное состояние счетчик 27через его второй вход.При поступлении на первый входсчетчика 2 следующих и импульсов онпереполняется и импульс с его выходапоступает на второй вход блока 4 управления и на.первый вход счетчика29, который под его воздействиемпереполняется и на его выходе появляется сигнал единичного уровня. Подего воздействием коьщутатор 26 соединяет свой выход с вторым входом,Кроме того, этот сигнал разрешаетпрохождение ТИ с выхода умножителя23 частоты через элемент И 22 натретий выход блока 4 управления. Те -перь ТИ с выхода умножителя 23 частоты до окончания работы устройствапоступают на третий выход блока Иуправления и, кроме того, через коммутатор 26 на первьп вход счетчика27, который осуществляет их подсчети через каждые и тактов выдает насвой выход единичный импульс, кото-.рый поступает на второй выход блока4 управления.Счетчик 30 на протяжении работыустройства осуществляет подсчет тактовых импульсов, поступающих на егопервый вход от генератора 24 тактовыхимпульсов и Формирует на своем выходеединичный сигнал через каждые и тактов. Этот сигнал поступает на четвертьп выход блока 4 управления, т.е,на четвертом выходе блока 4 управления появляется единичный импульс приокончании приема каждого повтора КК,При переполнении счетчика 30 импульсс его выхода через второй вход счетчика 30 сбрасывает его в исходноесостояние,При поступлении на первьп входблока 4 управления сигнала "1(онец приема" он воздействует на первьп входтриггера 25, которьп при этом переходит в нулевое состояние и на еговыходе появляется сигнал нулевогоуровня, выключающий генератор 24 тактовых импульсов.Кроме того, сигнал "Конец приема"поступает на второй вход счетчика 29и сбрасывает его. Таким образом блокуправления переходит в исходноесостояние, описанное выше.Формула изобретения1 Устройство для обнаружения и исправления ошибок, содержащее блок коммутации, первьп и второй регистры сдвига,. о т л и ч а ю щ е е с я тем, что, с целью повьппения достоверности и быстродействия устройства, в него введены блок управления, блок исправления ошибок, элемент НЕ, элемент ИЛИ, сумматор по модулю два и первьп и второй элементы И, первые входы которых объединены с первыми входами первого регистра сдвига и блока коммутации и подключены к ин 1640814 12формационному входу устройства, пер-, вый выход блока управления подключен непосредственно к вторым входам блока коммутации и первого элемента И и через элемент НЕ к второму входу второго элемента И, выход которого и выход первого элемента И подключены соответственно к первым входам сумматора по Модулю два и блока исправления ошибок, выход которого подключен к третьему входу блока коммутации, вЫход которого является выходом устройства, второй, третий и четвертый выходы. блока управления и первые15 выходы второго регистра сдвига подключены соответственно к вторым - пятым входам блока исправления ошибок, выход первого регистра сдвига .подключен к второму входу сумматора по модулю .два, выход которого соединен с первым входом элемента ИЛИ, выход которого подключен к первому входу второго регистра сдвига, второй выход которого подключен к второму входу элемента ИЛИ, пятый выход блока управления подключен к вторым входам первого и второго регистров сдвига, третьи входы которых объединены с первым входом блока управления 30 и шестым, входом блока исправления ошибок и подключены к входу "Конец приема" устройства, второй вход блока управления является входом "Начало приема" устройства.2, Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок исправления ошибок содержит первый - третий регистры сдвига, коммутатор, элемент И, первый и второй элементы ИЛИ, дешифратор, сумматор, счетчик импульсов и группу ключей, первые входы которой являются пятыми входами блока, второй вход объединен с первым входом первого элемента ИЛИ 45 и является четвертым входом блока, выходы группы ключей подключены к первым входам первого регистра сдвига и входам сумматора, выходы которого подключены к входам дешифратора, вы 50 ходы которого подключены к первым входам счетчика импульсов, второй вход и выходы которого подключены соответственно к четвертым входам блока и первым входам второго регистра сдвига, второй и третий входы и выход которого подключены соответственно к выходам первого элемента ИЛИ и элемента И и первому входу коммутатора, выход второго элемента ИЛИ подключен к первому входу третьего регистра сдвига, выход которого соединен с вторыми входами второго элемента ИЛИ и коммутатора, выход первого регистра сдвига подключен к своему второму входу, первому входу элемента И и третьему входу коммутатора, выход которого является выходом блока, второй вход второго элемента ИЛИ является первым входом блока, второй вход третьего регистра сдви а объединен с вторым входом первого элемента ИЛИ и третьими входами счетчика импульсов и первого регистра сдвига и является шестым входом блока, второй вход элемента И объединен с третьим входом третьего регистра сдвига и четвертым входом первого регистра сдвига и является третьим входом блока.3. Устройство по и. 1, о т л и - ч а ю щ е е с я тем, что блок управления содержит первый и второй триггеры, первый - третий счетчики импульсов, коммутатор, генератор тактовых импульсов, умножитель частоты и элемент И, выход первого триггера подключен к входу генератора тактовых импульсов, выход которого является пятым выходом блока и подключен непосредственно к первым входам коммутатора и первого счетчика импульсов и через умножитель частоты к первому входу элемента И и второму входу коммутатора, выход которого подключен к первому входу второго счетчика импульсов, выход которого является вторым выходом блока и подключен к второму входу второго счетчика импульсов и первым входам третьего триггера и третьего счетчика импульсов, выход которого подключен к третьему входу коммутатора и второму входу элемента И, выход которого является третьим выходом блока, первый вход первого триггера объединен с вторым входом третьего счетчика импульсов и является первым входом блока, вторые входы триггеров объединены и являются вторым входом блока, выход первого счетчика импульсов подключен к своему второму входу и является четвертым выходом блока, выход второго триггера является первым выходом блоиа,1640814 иг. 2 иг.5 акт азаренк Зака Производственно-издательский комбинат "Патент" арина, 101 город,022Госуда оставитель О. Тюринаехред М.Моргентал Корректор Н.Ревска Тираж 464 Подписное венного комитета по изобретениям и открытиям при 113035, Москва, Ж, Раушская наб., д. 4/5