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

 

Р. фи ли,.т ме. МЕм»

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

<>508290

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву— (22) Заявлено 12.02,74 (21) 1998325/18-24 с присоединением заявки №вЂ” (23) Приоритет— (43) Опубликовано 30.03.76. Бюллетень № 12 (45) Дата опубликования описания 02.02.77 (51) М.К ч з 6 08 С 25/00

Гвсударственный комитет

Совета Министров СССР по ленам . изобретений н открытий (53) УДК 681.325.7 (088.8) (72) Авторы изобретения

А. А. Давыдов, Г. М. Тененгольц, В. И. Эзакели, Г. А. Бунатян, Э. М. Гендлер и Л. В. Тепляшина (7)) Заявитель

Ордена Ленина институт проблем управления (54) УСТРОЙСТВО

ДЛЯ ДЕКОДИРОВАНИЯ КОДОВ

Изобретение относится к электронным дискретным устройствам систем автоматики, телемеханики, вычислительной техники и связи.

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

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

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

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

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

16 определения вида искажения.

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

Зо третьим входом блока определения вида

508790

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

Функциональная схема предлагаемого устройства представлена на чертеже, где: 1 анализатор; 2 — блок выделения информационной части сообщения; 8 — схема сравнения; 4 — блок определения вычета; 5 — блок локализации ошибки; б — блок коррекции;

7 — блок выделения четных и нечетных позиций; 8 — блок контроля на четность; 9— блок подсчета количества единиц; 10— блок определения искажений в контрольной части сообщения; 11 — блок итеративого вычисления суммы; 12 — блок вычитания; 18— первая до полнительная схема сравнения;

14 — третья дополнительная схема сравнения; 15 — вторая дополнительная схема сравнения; 1б — элемент «И», 17 — блок определения начала пакета ошибок; 18 блок определения вида искажения; 19— коммутатор; 20, 21 — выходы блока 7; 22— выход «Больше» схемы 18; 28 — выход

«Меньше» схемы 18; 24 — первый выход схемы 15 (выход «Больше»); 25 — второй выход схемы 15 (выход «Меньше»); 2б — третий выход схемы 15 (выход «Равно»); 27, 28 — выходы блока 17; 29 — выход блока 18, выдающий информацию о виде искажения.

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

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

Х1 Х г ° ° Хгг Хгг XR Хгг+3 ° ° ° /г+т-)-2 /г+т+2 т".

X х/г+т+4 Хф+т+5 1 О.

Здесь х; — некоторый двоичный символ; хь

xf, — информационные символы; х +з, ..., >R+i+2 — двоичная запись наименьшего неотрицательного вычета 1 обобщенного веса

Qixl последовательности информационных

i=! символов (вычет определяется по модулю

2, 4» 1); +R+rt4 и хг+,1.; — суммы по модулю два информационных символов, стоящих на нечетных и четных позициях соответственно.

Принимаемая устройством двоичная последовательность одновременно поступает в анализатор 1 и в блоки 2 и 7. Анализатор 1 анализирует k+r+6-й символ последовательности. Когда этот символ равен «1», то выпадений нет и возможны только несимметрические ошибки. Если указанный символ равен «0», то произошло одиночное выпадение символа. ,Рассмотрим работу устройства в обоих отмеченных случаях.

П е р в ы и сл у ч а й. 1(+r+6-й символ принятой последовательности равен единице.

Первые k+r+5 символов принятой последовательности с выхода анализатора 1 поступают в блоки 4, 5 и 10. В блоке 10 проверяется,,противоположны ли друг другу значения

k+r+2-го и k+r+3-го символов гпоследовательности. Если эти значения совпадают, то имеют место ошибки в контрольной части сообщения, а в информационной части ошибок нет. Если указанные значения противоположны, то й+г+2-й символ последовательности не искажен, и ошибки в информационной части возможны. Информация о результате сравнения k+ r+2-го и k+ r p3-го символов и информация о результате анализа й+г+6-го символа гноступают соответственно из блока

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

f: т — g,ix, +, .х г+2+; 2 - по модулю 2

i=) i=1 (х, — -й символ принятой, последовательности). Вычет st с выхода блока 4 подается в блоки 12 и 17, в схемы 18, 14, 15 m в коммутатор 19. Для рассматриваемого случая важна работа блока 17, схемы 14 и коммута508790

Таблица 1

М х

Cl о %

Я Я

8 ? о

Условия, при которых имеет место искажение данного вида

Вид искажения

1, Одна ошибка типа 1 — «О, S!)0, S=1

Одна ошибка типа 0-«1 Si(O, S=1

Две смежные несимметрические ошибки с >О типа 1 — «О

Две смежные несимметрические ошибки типа 0 — «1

Si(O, S=2 тора 19. Схема 14 вычет sl сравнивает с нулем, и информация о результате сравнения поступает из схемы 14 в блок 18. В блоке 17

)Я!! — 1 вычисляются две величины: S / и

Эти величины соответственно с выходов 27 и

28 блока 17 поотупают в коммутатор 19. Блок

7, получив из анализатора 1 информацию о результате анализа k+r+6-го символа, выделяют среди первых k символов принимаемой последовательности символы, стоящие на четных и .нечетных, позициях. Четные символы попадают на выход 20, нечетные символы— на выход 21. Кроме того, на,выход 20 проходит k+r+5-й символ принимаемой последовательности, а на выход 21 k+r+4-й символ.

Блок 8 вычисляет две суммы по модулю два:

sg и за, причем sg — сумма двоичных символов, появившихся на выходе 20 блока 7, s3— сумма двоичных символов, появившихся на выходе 21 блока 7. Значения s> и ss передаются из блока 8 в блок 18.,В блоке 18 на основе ни формации, поступающей из блоков 8 и 10, из анализатора 1,и схемы 14, определяется вид искажения. При этом логические блоки, входящие в состав блока 18, реализуют следующий алгоритм.

Поскольку k+ r+ 6- и символ, принятой последовательности равен единице, то,выпаде,ний нет. Вычисляется сумма s=s, +sz. Ошибок в ни формационной части нет, если выполняется любое из условий: значения й+г+2-го и k+r+3-го символов принятой последовательности совпадают; s=sl О; sl — — О, з Ф О;

sl+ О, s=0.

Сигнал об отсутствии ошибок в информационной части поступает из блока 18 в блок

2, который выделяя первые k символов принятой последовательности, выдает их на .выход устройства. На этом процесс декодирования заканчивается.

Если значения k+r+2-го,и /г+г+3-го символов принятой последовательности противоположны и s + О, s э 0, то ошибки в информационной части есть. Блок 18 определяет ,номер и вид искажения в информационной части в соответствии с табл. 1.

Номер искажения поступает с выхода 29 блока 18 в блоки 6 и коммутатор 19. Если в информационной части одна ошибка (т. е. искажение № 1,или 2), то коммутатор 19 .про5 пускает в блоки 6 информацию с выхода 27 блока 17, т. е. 5>/. Когда в информационной части две смежные несимметрические ошибки (т. е. искажение № 3 или 4), коммутатор 19 пропускает в блок 6 информацию с выхода 28

10 (Я, — 11 блока 17 т. е. 2 ). Искаженная информационная часть сообщения, поступившая в блок 6 из блока 5, исправляется в блоке б:в

15 соответствии с данными, попавшими в блок 6 из блока 18 и коммутатора 19. При этом данные из коммутатора 19 рассматриваются как номер начала пакета ошибок. Исправленная информационная последовательность выдает20 ся из блока 6 на выход устройства.

В то р о и сл уч ай. K+r+6-й символ принятой последовательности равен нулю.

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

11. Блок 5 выделяет из сообщения искаженную информационную часть и передает ее в

40 блок 6. Блок 4 подсчитывает наименьший неотрицательный вычет sl выражения

I — 1 г —. 1х, + YÓ х +!+; 2 — по модулю 2 .

i=! i=l

Этот вычет с выхода блока 4 поступает в блоки 12 и 17, в схемы 18, 14, 15 и в коммутатор 19. Для рассматриваемого случая важна работа блока 12, схем 18, 15 и коммутатора

50 19. На входы блока 12;и схемы 18, кроме вычета s подается из блока 9 число w, равное количеству единиц .в,первых символах принятой последовательности. В блоке 12 подсчитывается разность и, = s,— w — 1. Значение

55 этой разности из блока 12 передается в коммутатор 19. Схема 13 сравнивает числа s, и

w. Если s!)w, то выдается сигнал на выходе

22, а если s,(w, то появляется сигнал на выходе 23. Эти сигналы поступают в блок 18.

Из анализатора 1 информация о результате анализа А+г+6-го символа принятой последовательнсст1! попадает в блоки 18 и 7. Блок

7, получив указанную информацию, выделяет среди первых k — 1 символов принимаемой

55 последовательности символы, стоящие на чет508790

Таблица 2

Условия, прн которых имеет место искажение данного вида

Номер искажения

Вид искажения

S=1

n S!)W

Выпадение единицы, слева от которой в послег

l довательностп х ) хя .. х размещено пр нулей

Выпадение нуля на i-й позиции и одновременно ошибка типа С вЂ” >! на — 1-й позиции.

Номер удовлетворяет условиям:

x ;, = 1; — (i — 1) + n) — — S»

/$!, если S, < w

1$! — 2л, если S, ) n

S=1

$)(Ж или

S!)n

S=O

S,(W

Выпадение нуля, справа от которого в последовательности х) xz ... х )! — ) размещено S! единиц

$=0

Выпадение единицы на !-й позиции и одновременно ошибка типа 1-+О íà i-й позиции.

Номер i удовлетворяет условиям: х i ) = 0; 2i — 1 + п; = S, S!) W ных и,нечетных позициях. Четные символы поступают на выход,20,,нечетные символы— на выход 21. Кроме того, на выход 20 проходит k+r+3-й символ принимаемой последовательности, а на выход 21 — k+r+4-й символ. Блок 8, как и в предыдущем случае, вычисляет две суммы по модулю два: sz u

s — и передает значения этих сумм в блок

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

Поскольку й+ г+ 6-й символ принятой последовательности равен нулю, то одиночное

Отметим, что искажение вида «выпадение нуля» на -й позиции и одновременно ошибка типа 1 0 на i — 1-й позиции сводится к искажению № 5. А искажение вида к<выпадение единицы» на )-й позиции и одновременно оши!бка типа 0 -+ 1 на 11-й позиции сводится к искажению № 7. Поэтому отмеченные искажения отдельно:в таблице .не рассматриваются.

Номер искажения поступает с,выхода 29 блока 18 в !блоки 11, б и коммутатор 19. Если произошло искажение № 6 или 8, то включается блок 11.

Рассмотрим вначале ра!боту блока 11 при наличии искажения № 6. В этом случае блок

1!1 итеративно вычисляет сумму вида q(i) =

= — (i — 1) +. а; йо следующему алгоритму.

В последовательности х, х ... х q ) поочередно .выбираются позиции, .на которых расположены единицы. Выбор позиций осуществляется слева .направо. Каждая выбранная выпадение символа имеет место. Факт,наличия сигналов на выходах 22, 28 означает, что на выходы схемы 18, а, следовательно, и на входы блоков 4 и 9, ин!формация .поступила.

Последнее означает, что имеет место выпадение символа в,информационной части, так как в противном случае из схемы 8 в блоки 4 и 9 сигналы не подаются. Вычисляется сумма

10 по модулю два s — язв -зз, а затем определяется в соответствии с табл. 2 вид и номер искажения в информационной части (Через и; в табл. 2 обозначено количество единиц в последовательности х) х. ... х p ), расположенных правее i — 1-й позиции). позиция рассматривается в качестве i — 1-й позиции и для каждой выбранной позиции вычисляется сумма гр()). Значение ) — 1 проходит !на информационный, вход элемента !б, а значение ср()) — в схему 15, где сравнивается со значением $„поступивщим в схему

15 из блока 4. Если )p(i) )S), то с выхода 24 схемы 15 на вход блока 11 поступает сигнал, свидетельствующий о необходимости выбрать новую позицию и вычислить для этой .новой позиции сумму cp(i). Работа блока 11 продолжается. Если же ср(г) =5„то сигнал с выхода 2б схемы 15 поступает,на управляющий вход элемента 1б. Элемент 1б открывается и пропускает значение i — 1 ., на вход коммутатора 19. Работа блока 11 закончена.

Рассмотрим теперь ра)боту блока 11 при наличии искажения № 8. В этом случае блок

11 ите!ративно вычисляет сумму вида

/(г) =2; + n; по алгоритму, аналогичному алгоритму вычисления суммы <(i) Отличие

508790

35

45

50 в том, что в качестве i 1-й позиции выбираются позиции с символом «О», а сигналом для продолжения работы блока 11 и выбора новой позиции является сигнал с выхода 25 схемы 15. Выбор позиций при вычислении суммы () также осуществляется слева направо, а значение i — 1 через элемент 1б также,поступает в коммутатор 19.

Коммутатор 19, получив,из блока 18 информацию о виде искажения, пропускает в блок б либо число по (в случае искажения № 5), либо число i — 1 (при искажениях № 6, 8), либо число S> (если, искажение № 7).

Блок б, приняв от коммутатора указанные числа .и получив из блока 18 номер искажения, осуществляет коррекцию, искаженной информационной части соо бщения, поступившей в блок б,из блока 5. Коррекция проводится в соответствии с табл. 2. Исправленная информационная последовательность выдается,из блока 6 на выход устройства.

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

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

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

«И», третий выход второй дополнительной схемы сравнения соединен с вторым входом элемента «И», выход которого соединен с шестым входом коммутатора, выход коммутатора соединен с третьим, входом блока коррекции, выход которого соединен с выходом устройства.

508790

Составитель А. Давыдов

Техред Т. Лященко

Корректор Л. Орлова

Редактор И. Грузова

Тираж 830 Подписное

Совета Министров СССР и открытий наб., д. 4/5

Заказ 1086/1649 Изд. Ув 1789

ЦНИИПИ Государственного комитета по делам изобретений

Москва, Ж-35 Раушская

Тип. Харьк. фил. пред. сПатент»