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

оэ «и

о сю

4

10

Г

15

10001010110 10101001110

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

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

На фиг. 1 представлена функциональная схема устройства; на фигс 2 функциональная схема блока исправления ошибок; на фиг. 3 - функциональная схема блока управления.

Устройство содержит блок 1 коммутации, элемент И 2, блок 3 исправления ошибок, блок 4 управления, элемент НЕ 5, элемент И 6, регистр 7 сдвига, сумматор 8 по модулю два, элемент ИЛИ 9, регистр 10 сдвига.

Блок 3 содержит элемент ИЛИ 11 регистр 12 сдвига,коммутатор 13(элемент ИЛИ 14,регистр 15 сдвига,счетчик 1 6 импульсов,элемент И 1 7,дешифратор 18,сумма-2г 101010101 тор 19fperHCTp 20 сдвига,группу 2t ключей. 1010101 1

Сумматор 19 предназначен для формирования двоичного кода числа т+1, где т - число единиц в предполагаемом синдроме ошибок.

Дешифратор 18 предназначен для Формирования двоичного числа 2т, которое определяет коэффициент переполнения счетчика 16.

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

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

в ПСО одну из 2 комби

Например,

первый пов

КК

второй пов

КК

ПСО

20

0010001 1000 100010001 10001001 1 100010101 1000101 1 101010001 1 0 t 0 1 0 0 1

При этом каждый вариант КК пров ряется на наличие ошибок, Если посл перебора всех вариантов КК ошибки и правлены не будут, то осуществляет прием третьего повтора КК, -формиро ние очередного ПСО с учетом трех п второв и перебор возможных вариант КК с проверкой их на наличие ошибо Если после этого ошибки исправлены 35 не будут, осуществляется прием 4-г

повтора КК и ТоД. Из сказанного сл

i

дует, что при М-м повторе КК ошибки не будут исправлены в том случае,е

30

Блок 4 управления содержит элемент 40 хотя бы в одной позиции КК во всех

22 И, умножитель 23 частоты, генератор 24 тактовых импульсов, триггер 25. коммутатор 26, счетчик 27 импульсов, триггер 28,счетчики 29 и 30 импульсов.

, Генератор 24 тактовых импульсов д предназначен для формирования тактовых

- импульсов с частотой fт, соответствующей тактовой частоте поступления в устройство информационных символов.

Умножитель 23 частоты предназначен для Формирования тактовых импульсов с частотой ff k- fT, на которой осуществляется работа.л

Устройство реализует следуютрй метод исправления ошибокь Исправление ошибок начинается после передачи второго повтора кодовой комбинации (КК). Сначала осуществляется поразрядное сравнение первого и второго

М-повторах присутствует ошибочный с вол, т.е. вероятность декодирования М повторе КК равна.

v- -

Устройство работает следующим об разом

При поступлении первого повтора довой комбинации (КК) на информацио ный вход устройства на вход Начало приема подается единичный импульс, соответствии с которым единичный си нал с выхода блока 4 управления ком мутирует выход блока 1 коммутации с его первым входом и открывает элеме 5- И 2. Кроме того, по сигналу Начало приема с пятого выхода блока 4 упр ления начинают поступать тактовые и пульсы. Первый повтор КК через элем

50

0

Г

5

10001010110 10101001110

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

в ПСО одну из 2 комбинаНапример,

первый повтор

КК

второй повтор

КК

ПСО

0

0010001 1000 100010001 10001001 1 100010101 1000101 1 101010001 1 0 t 0 1 0 0 1

101010101 1010101 1

При этом каждый вариант КК проверяется на наличие ошибок, Если после перебора всех вариантов КК ошибки исправлены не будут, то осуществляется прием третьего повтора КК, -формирование очередного ПСО с учетом трех повторов и перебор возможных вариантов КК с проверкой их на наличие ошибокt Если после этого ошибки исправлены не будут, осуществляется прием 4-го

повтора КК и ТоД. Из сказанного слеi

дует, что при М-м повторе КК ошибки не будут исправлены в том случае,если

хотя бы в одной позиции КК во всех

М-повторах присутствует ошибочный символ, т.е. вероятность декодирования на М повторе КК равна.

v- -

Устройство работает следующим образом

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

И 2 поступает на первый вход блока 3 исправления ошибок и записывается в него, а также, под воздействием импульсов сдвига, действующих на вход регистра 7 сдвига,записывается в него Кроме того, первый повтор КК через блок 1 коммутации поступает на выход устройства для проверки на наличие ошибок.

Если в КК будут обнаружены ошибки, то осуществляется прием следующего повтора КК„ При этом на первом выходе блока 4 управления действует нулевой сигнал, в соответствии с которым блок 1 коммутации коммутирует выход с третьим входом. Этот же сигнал закрывает элемент И 2 и через элемент НЕ 5 открывает элемент И 6.

Второй повтор КК под воздействием импульсов сдвига записывается в первый регистр 7 сдвига,а также поступает через второй элемент И на второ вход сумматора 8 по модулю 2, где поразрядно суммируется с первым повтором КК, поступающим на его первый вход из регистра 7 сдвига. Результат сложения первого и второго повторов КК через элемент ИЛИ 9 под воздействием импульсов сдвига, поступающих на второй вход второго регистра 10 сдвига записывается в этот регистр. Таким образом, в регистре 10 сдвига записывается двоичная последова- тельность, в которой Э соответствует совпадению символов одноименных разрядов первого и второго повторов КК, а 1 - их несовпадению т.е„ единицами помечаются ненадежные символы, в которых с наибольшей вероятностью могут быть ошибки (в дальнейшем будем называть эту последовательность предполагаемым синдромом ошибок - ПСО)и

После окончания приема второго повтора КК со второго и третьего выходов блока 4 управления на соответствующие входы блока 3 исправления ошибок поступают единичные импульсы, а с четвертого выхода блока 4 управления на четвертый вход блока 3 исправления ошибок начинают поступать тактовые импульсы с частотой Јт( k-fT, где fr - тактовая частота приема КК: К МО3 - 10 (увеличение тактовой частоты для обработки КК в блоке 3 исправления ошибок обусловлено необходимостью реализации процедуры исправления ошибок в реальном

0

5

0

5

масштабе времени). Одновременно с этим из регистра 10 сдвига на третьи входы блока 3 исправления ошибок поступает в параллельном коде UCOt, После этого в блоке 3 исправления ошибок осуществляется перебор вариантов КК в соответствии с изложенным выше алгоритмом При этом каждый вариант КК с выхода блока 3 исправления ошибок через блок 1 коммутации поступает на выход устройства, где он проверяется на наличие ошибок.

В случае, если после приема второго повтора КК ошибки исправлены не будут, то осуществляется исправление ошибок с использованием третьего повтора КК. При этом второй ПСО формируется следующим образом. В сумматоре 8 по модулю два осуществляется поразрядное сложение второго повтора КК, поступающего из регистра 7 сдвига, и третьего повтора КК, поступающего через элемент И 6. Одновременно с этим третий повтор КК под действием импульсов записи записывается в регистр 7 сдвига. Результат сложения по модулю два второго и третьего пЬвторов КК поступает на первый вход элемента ИЛИ 9 на второй вход которого синхронно поступает ПСОд с второго выхода регистра 10 сдвига (под воздействием импульсов сдвига выхода блока 4 управления)0 Таким образом, в регистр 10 сдвига записывается очередной ПС02, учитывающий первый, второй и третий повторы КК. Далее осуществляется исправление ошибок аналогично описанной выше процедуре.

Если при этом ошибки исправлены не будут, то осуществляется прием четвертого повтора КК, формирование ПСОд, исправление ошибок и т„д.

В случае полного исправления оши- $ бок на вход Конец приема устройства подается единичный сигнал, который сбрасывает в исходное состояние регистры / и 10 сдвига и элементы блока 3 исправления ошибок и блока 4 управления. Устройство готово к следующему циклу работы

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

В исходном состоянии счетчик 16, регистры 12, -15 и 20 сдвига находятся в сброшенном состоянии Первый повтор КК,.поступающий на первый вход блока исправления ошибок, записьшяет0

5

0

0

5

ся через элемент ИЛИ 11 в регистр 12 сдвига под воздействием импульсов сдвига, поступающих на его пятый вход из блока 4 управления. Процедур исправления ошибок после первого повтора не осуществляется„ После приема второго повтора КК сформированный ПСО в параллельном коде поступает через пятый вход блока 3 исправления ошибок на вторые входы группы 21 ключей, на вход которого из блока 4 управления через четвертый вход блок 3 исправления ошибок поступает единичный импульс, разрешающий прохож- дение ПСО на входы сумматора 19 и четвертые входы регистра 20 сдвига, куда последний и записывается. В сум маторе 19 осуществляется сложение символов TlCO и прибавление к ним единицы,т,ео на выходы сумматора 19 действует двоичный код, соответствующий количеству единиц в ПСО, увеличенное на единицу (т+1).

В соответствии с этим кодом, по- ступающим на входы дешифратора 18, на (т+1) выходе его действует единичный сигнал, что соответствует двоичному коду числа 2т. Двоичный код этого числа поступает на вторые входы счетчика 16 и воспринимается им как коэффициенты переполнения. На первый вход счетчика 16 поступают единичные импульсы с периодом n- fT) , под воздействием которых счетчик последова- тельно принимает одно из 2 состояний, которые записываются в регистр 15 сдвига.

Одновременно с этим на третьи входы регистров 12 и 20 сдвига начинают поступать с первого входа блока 3 исправления ошибок импульсы сдвига, под воздействием которых из этих регистров осуществляется последовательное считывание записанных в них ком- бинаций на первый и третий вход коммутатора 13 соответственно. Третий вход коммутатора 13 является управляющим: при воздействии на него 1 импульс сдвига проходит через открывшийся элемент И 17 на третий вход (сдвига) регистра 15 сдвига и под его воздействием на выход этого регистра считывается содержимое его первого разряда,которое через коммутатор 13 поступает на выход блока исправления ошибок; при воздействии О элемент И 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 переходят в единичное состояние Сигнал единичнего уровня с выхода триггера 28 поступает на первый выход блока 4 управления, а сигнал единичного уровня с выхода триггера 25 запускает генератор 24 тактовых импульсов, который начинает формировать импульс с тактовой частотой, равной частоте поступления символов КК на вход устройства Тактовые импульсы (ТИ) поступают на четверть выход блока 4 управления, а также на вход умножителя 23 частоты на выходе которого действуют ТИ с частотой в К раз больше, чем на выходе (К л- 103 - 104)„ Кроме того, ТИ с выхода генератора 23 тактовых импульсов поступают на первый вход счетчика 30, коэффициент переполнения которого равен п (п - разрядность КК) и на первый вход коммута- тора 26, который в зависимости от сигнала,действующего на его третий вход, соединяет свой выход с первым или вторым входом: при 1 - с вторым входом; при О - с первым.

Так как в исходном состоянии счетчик 29 сброшен, то на третьем входе коммутатора 26 действует сигнал нулевого уровня, в соответствии с которым на его выход поступают сигналы с первого входа.

Импульсы от генератора 24 тактовых импульсов через коммутатор 26 поступают на первый вход (счетный) счетчика 27, коэффициент переполне- ния которого равен п. При поступлении n-го импульса на первый вход счетчика 27 он переполняется и на ег выходе появляется импульс, который поступает на второй выход блока 4 управления, на второй вход триггера

28,переводя его в нулевое состояние (на первом выходе блока 4 управления действует сигнал нулевого уровня) и на первый вход счетчика 29, коэффициент переполнения которого равен двум Этот же импульс сбрасывает в исходное состояние счетчик 27 через его второй вход.

При поступлении на первый вход счетчика 27 следующих п импульсов он переполняется и импульс с его выхода поступает на второй вход блока 4 управления и на первый вход счетчика

29,который под его воздействием переполняется и на его выходе появляется сигнал единичного уровня. Под его воздействием коммутатор 26 соединяет свой выход с вторым входом

Q 5 0 5

0

,. о

0

Кроме того, этот сигнал разрешает прохождение ТИ с выхода умножителя 23 частоты через элемент И 22 на третий выход блока 4 управления. Теперь ТИ с выхода умножителя 23 частоты до окончания работы устройства поступают на третий выход блока И управления и, кроме того, через коммутатор 26 на первый вход счетчика 27, который осуществляет их подсчет и через каждые п тактов выдает на свой выход единичный импульс, который поступает на второй выход блока 4 управления о

Счетчик 30 на протяжении работы устройства осуществляет подсчет тактовых импульсов, поступающих на его первый вход от генератора 24 тактовых импульсов и формирует на своем выходе единичный сигнал через каждые п тактов. Этот сигнал поступает на четвертый выход блока 4 управления, т0е. на четвертом выходе блока 4 управления появляется единичный импульс при окончании приема каждого Повтора КК„ При переполнении счетчика 30 импульс с его выхода через второй вход счетчика 30 сбрасывает его в исходное состояние.

При поступлении на первый вход блока 4 управления сигнала Конец приема он воздействует на первый вход триггера 25, который при этом переходит в нулевое состояние и на его выходе появляется сигнал нулевого уровня, выключающий генератор 24 та.к- товых импульсов„

Кроме того, сигнал Конец приема поступает на второй вход счетчика 29 и сбрасывает его. Таким образом блок 4 управления переходит в исходное состояние, описанное выше.

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

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

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

0

5 ч

ИЛИ и элемента И и первому входу коммутатора, выход второго элемента ИЛИ подключен к первому входу третьего регистра сдвига, выход которого соединен с вторыми входами второго элемента ИЛИ и коммутатора, выход первого регистра сдвига подключен к своему второму входу, первому входу элемента И и третьему входу коммутатора, выход которого является выходом блока, второй вход второго элемента ИЛИ является первым входом блока, второй вход третьего регистра сдвига объединен с вторым входом первого элемента ИЛИ и третьими входами счетчика импульсов и первого регистра сдвига и является шестым входом блока, второй вход элемента И объединен с третьим входом третьего регистра сдвига и четвертым входом первого регистра сдвига и является третьим входом блока.

3. Устройство по п. 1, о т л и - а ю щ е е с я тем, что блок уп0

5

0

5

0

5

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

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