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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)5 Н 03 N 13/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, Фиг.1

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

Н А 8ТОРСНОМУ СВИДЕТЕЛЬСТВУ (21) 4483097/24 (22) 12.07.89 (46) 07.04„91. Бюл„ Р 13 (72) ll.E. Глаэин и С.И„ Иванов (53) 681.325(088.8) (56) Авторское свидетельство СССР

Я - 1138947, кл. Н 03 М 1/00, 1982. (54) YCTPOPCTBO ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ ОШИБОК (57) Изобретение относится к технике передачи данных и может быть иснользо,SU, 1640814 А1 вана в системах передачи дискретной информации по каналам низкого качества для исправления ошибок при многократном повторении сообщений. 1(елью изобретения является повышение быстродействия и достоверности устройства. Устройство содержит блок 1 коммутации, элементы И 2 и 6, блок 3 исправления ошибок, блок 4 управления, элемент НЕ 5, регистры 7 и 10 сдвига, сумматор 8 по модулю два, элемент ИЛИ 9.. 2 з.п. ф-лы, 3 ил.

1640814

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

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

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

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

Блок 3 содержит элемент ИЛИ 11,регистр 12 сдвига, коммутатор 13,элемент

ИЛИ 14 регистр 15 сдвига, счетчик 16 импульсов, элемент И 17»дешифратор 18,сумма-25 тор 19,регистр 20 сдвига, группу 21 ключей.

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

Р ешифр ат ор 18 пр една з нач ен для формирования двоичного числа 2m которое определяет коэффициент переполнения счетчика 16 °

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

Елок 4 управления содержит элемент 4

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

Генератор 24 тактовых импульсов 45 предназначен для формирования тактовых .импульсов с частотой К, соответствующей тактовой частоте поступления в устройство информационных символов.

Умножитель 23 частоты предназначен для формирования тактовых импульсов с частотой Гт = k Гт, на.которой

1 осуществляется работа.

Устройство реализует следующий метод исправления ошибок. Исправление ошибок начин"";åòñÿ после передачи

55 второго повтора кодовой комбинации (КК) . Сначала осуществляется поразрядное сравнение первого и второго повторов КК и формирование предполага емого синдрома ошибок (ПСО) разрядностью и, в котором "0" соответствует совпадению символов одноименных раэрядов первого и второго повторов

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

"единицей" в ПСО одну из 2 комбинаций "0" и " 1", Например, 1 0 0 0 1 0 1 0 1 1 0 — первый повтор

КК

1 0 1 0 1 0 0 1 1 1 0 — второй повтор

KK

00100011000 — ITCH

1000101 1 1 10

10101001 1 10

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

КК с проверкой их на наличие ошибок, Если после этого ошибки исправлены не будут, осуществляется прием 4-го повтора КК и т.д. Из сказанного сле1 дует, что при M-м повторе КК ошибки . не будут исправлены в том случае, если хотя бы в одной позиции КК во всех

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

M KK равна. р = (1 1гп)И

Дм

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

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

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 исправления ошибок начинают поступать тактовые импульсы с частотой f

= k Ет, где fz — тактовая частота приема КК: К 10 — 10 (увеличение ф тактовой частоты для обработки КК в блоке 3 исправления ошибок обусловлено необходимостью реализации процедуры исправления ошибок в реальном

14

6 масштабе времени), Одновременно с этим из регистра 10 сдвига на третьи входы блока 3 исправления ошибок поступает в параллельном коде ПСО .

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

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

Таким образом, в регистр 10 сдвига записывается очередной ПСО, учитывающий первьп, второй и третий. повторы КК. Parsee осуществляется исправление ошибок аналогично описанной выше процедуре.

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

ПСО, исправление ошибок и т.д.

В случае полного исправления ошибок на вход "Конец приема" устройства подается единичный сигнал, который сбрасывает в исходное .состояние регистры i и 10 сдвига и элементы блока:

3 исправления ошибок и блока 4 управления. Устройство готово к следующему циклу работы.

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

В исходном состоянии счетчик 16, регистры 12 15 и 20 сдвига находятЭ

I ся в сброшенном состоянии. Первый повтор КК,.поступающий на первьп вход блока исйравления ошибок, записы ает1640814 ся через элемент ИЛИ 11 в регистр 12 сдвига под воздействием импульсов сдвига, поступающих на его пятый вход из блока 4 управления. Процедура 5 исправления ошибок после первого повтора не осуществляется. После приема второго повтора КК сформированный

ПСО в параллельном коде поступает

|через пятый вход блока 3 исправления 10 ошибок на вторые входы группы 21 ключей, на вход которого из блока 4 управления через четвертый вход блока

3 исправления ошибок поступает единичный импульс, разрешающий прохож- 15 дение ПСО на входы сумматора 19 и четвертые входы регистра 20 сдвига, куда последний и записывается. В сум маторе 19 осуществляется сложение символов ПСО и прибавление к ним 20 единицы,т,е. на выходы сумматора 19 действует двоичный код, соответствующий количеству единиц в ПСО, увеличенное на единицу (в+1) .

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

15 сдвига.

Одновременно с этим на третьи входы регистров 12 и 20 сдвига начинают поступать с первого входа блока 3 исправления ошибок импульсы сдвига, под воздействием которых из этих регистров осуществляется последовательное. считывание записанных в них ком- 45 бинаций на первый и третий вход коммутатора 13 соответственно. Третий вход коммутатора 13 является управляюпдм: при воздействии на него "1." импульс сдвига проходит через открывшийся элемент И 17 на третий вход (сдвига) регистра 15 сдвига и под его воздействием на выход этого регистра считывается содержимое его первого разряда которое через комму1

55 татор 13, поступает на выход блока исправления ошибок; при воздействии

"0" элемент И 17 закрывается, не пропуская импульс сдвига на третий вход регистра 15, а содержимое первого разряда регистра 12 сдвига через коммутатор 13 считывается на выход блока.

3 исправления ошибок. Под воздействием импульсoH сдвига, поступающих на третьи входы регистров 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 управления импульса "Начало приема" триггеры ?5 и 28 переходят в единичное состояние. Сигнал единич1640814

)О ного уровня с выхода триггера 28 поступает на первый выход блока 4 управления, а сигнал единичного уровня с выхода триггера 25 запускает генератор 24 тактовых импульсов, который

5 начинает формировать импульс с тактовой частотой, равной частоте поступления символов КК на вход устройства.

Тактовые импульсы (ТИ) поступают на четвертьП1 выход блока 4 управления, а также на вход умножителя 23 частоты, на выходе которого действуют ТИ с частотой в К раз больше, чем на выходе (К и. 10Э вЂ” 10 )„ Кроме того, 15

ТИ с выхода генератора 23 тактовых импульсов поступают на nepal вход счетчика 30, коэффициент переполнения которого равен и (п — разрядность КК) и на первьп вход коммута- 20 тора 26, который в зависимости от сигнала, действующего на его третий вход, соединяет свой выход с первым или вторым входом: при "1" — с вторым входом; при "0" — с первым.

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

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

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

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

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

его воздействием коммутатор 26 соединяет свой выход с вторым входом.

Кроме того, этот сигнал разрешает прохождение ТИ с выхода умножителя

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

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

4 управления.

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

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

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

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

4 управления переходит в исходное состояние, описанное выше.

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

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

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

15 выходы второго регистра сдвига подключены coQTpeTcTBBHHO к вторым— пятым входам блока исправления ошибок, выход первого регистра сдвига подклк"ен g второму входу су атора 20

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

"Начало приема" устройства.

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

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

rrqpabm BxogoM nepaoro szeMeHTa ИЛИ 45 и является четвертым входом блока, выходы группы ключей подключены к первым входам первого регистра сдвига и входам сумматора, выходы которого подключены к входам дешифратора, вы50 ходы которого подключены к первым входам счетчика импульсов, второй вход и выходы которого подключены соответственно к четвертым входам блока и первым входам второго регистра сдвига, второй и третий входы и BbIxop, которого подключены соответственно к выходам первого элемента

ИЛИ и элемента И и первому входу коммутатора, выход второго элемента

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

3. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что блок управления содержит первый и второй триггеры, первый — третий счетчики импульсов, коммутатор, генератор тактовых импульсов, умножитель частоты и элемент И, выход первого триггера подключен к входу генератора тактовых импульсов, выход которого является пятым выходом блока и подключен непосредственно к первым входам коммутатора и первого счетчика импульсов и через умножитель частоты к первому входу элемента И и второму входу коммутатора, выход которого подключен к первому входу второго счетчика импульсов, выход которого является вторым выходом блока и подключен к второму входу второго счетчика импульсов и первым входам третьего триггера и третьего счетчика импульсов, выход которого подключен к третьему входу коммутатора и второму входу элемента И, выход которого является третьим выходом блока, первый вход первого триггера объединен с вторым входом третьего счетчика импульсов и является первым входом блока, вторые входы триггеров объединены и являются вторым входом блока, выход первого счетчика импульсов подключен к своему второму входу и является четвертым выходом блока, выход второго триггера является первым выходом блоиа, 1640814

Фиг,5

Составитель 0. Тюрина

Техред М.Моргентал

Корректор Н.Ревская

Редактор Н. Лазаренко

Заказ 1022 Тираж 464 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГЕНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101