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

 

(11)) ! 1 !

Социвлистнивсинх

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

I f .( (61) Доголнитель !0е к авт. свпд-...;.— (22) За.:влено IS.I I.7- : (21) 207660" ".! I

;51) М.Кл.- С 06 F I I/08

1-1 0 i 1 1 10 с присоединением заявки №вЂ” (23) Приоритет— (43) Опубликовано 30.08,76. Бюллетень Л" 32 (45) Дата опчбликованпя оппса:шя 21.10.7 (53) (К 691 ? iI 257:

;62; 04 147 (C88.8) (72) Автор

В. И. Кляч:".0 изоб:етенпя

i (7 I ) лаявпт, -ь

- 54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ О! -11503

В КОДОВОЙ b;OA".ÁÈHÀÖÈÛ

Изобретение относится к области передачи дав: ых и может быть применено в устройствах защиты от ошибок аппаратуры передачи да.l:Ih!x (ЛПД).

11звестны устройстоза для исправления и обнаружения ошибок в передаваемых сообщеОдно h3 из вест< ых устройств, зующсе метод порогозого декодирования, содержит регистр, логические и пороговые схемы н отличается, простотой реализации. Однако оно применимо для ограниченного класса кодоз, допускающих гороговое декодирование.

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

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

Кроме того, .во всех перечисленных выше устройствах при исправлении ошибок не испольСоюз Советских 1

l росс - Ыи,l

I

I

i

- 3 =:" "- h

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

Совета Министров СССР I !

IIo делен нзооретеннй и о IIPbtiHA зуется и. формация î ненадежных элемeIITax («стирания»), которая может быть полу:.ена при регистрации элсментов комбпнацщ „Для исправления I-крат::ых ошибок применяются корректирующие коды с кодовым расстоянием а =21+ 1.

Ниболее близким по технической сущности изобретению является устройство, содержащее однопзрогоз ю и двухпороговую схемы, сосдппе .Iill с с входом устройства, сумматор по модулю два. одпп .вход которого соединеч с выходом блока формирования полнпомов ошиоок, другой вход через последовательно соедпве..ные ы фсрнь.й и ос;03:юй блок

l5 памяти — с выходом однопороговой схемы, а выход — с первым входом элемента «1!», блок обнаружения ошиоок, первый зыход которо.о соединен с первым выходом устройства, в.эрой выход — с вторым входом элемента «11», 20 выход элемента «И» соединен с вторым выходом устройства.

Известное устройство исправляет t-Kpèãные ошибки при использовании корректпру 0щего кода с кодовым расстоянием d=t -I- I, 2 При этом из ошибок до l-кратных включиT 0. I bH 0 . . е ilI 0 I i T б hl T b u c LI p а в л 0 i! hl 0 LII I I á II:. I, обусловлепныс трансформированными элментамп, не попадающими в интервал стирания. Число таких опшбок очень незначительЗО но, так как в двоичном симметричном сти526898 р 3 10 щ л1 к 3!Н 3 л е В е!р О я TIH О с т ь т р 3 и с ф О р м 2 ци и

=»I0ì".iToB комби!нации Рт Вы!би р210т знасlителыно ме!ньшее верояпности стирания элемента ко!Мби!Нации

Рт(z S

S == Рь. -, д ; а в )0HTHocTb появле". ия ошибки данного Tиna определится выражением

P — C C q Р.q0 — 3)

1 где q —,зе;)оятность прави"!ü .-!ого приема элеме, !та комбинации.

Н::;с.-правляется н двухкратная ошибка еле;(ующего типа, обусловленная трансформ".цпей па интервале стирания Рз третьего элемента, правильного приема на интервале стирания q шестого элемента и трансформацией на интервале стирания Р> девятого элемента комби!нации, так как после регистрации третьего и шестого элементов счетчик стира!ний переполняется, закрывает ключ и «стирание» девятого элемента не .поступает в блок формирования полиномов ошибок. В,результате двухкратная ошибка (третий и девятый элементы) не исправляется. Число разли ) IIblx вариантов ошибок данного типа составляет.) ур .с г Г

> — и —

) l.

d а BOpOHTHocTb появления ошибки да !ного т.1па Определяется выражением где PB — вероятность стирания трансформированного элемента комбинации; q2 — вероят1-.ость стирания правилыно принятого элемента комбинации. Кроме того, в известном устройстве не иснравляются ошибки, стирания с которых частично или потностью не введены з блок фсрмиро!ва!Ния полиномоз ошиоок изза переполнения с IBò÷èêà стира!Ний. Покажем это на и!римере. При использова!Нии корректирующего (n, Iг) - кода с (1=3, исправляющего ошибки до кратности t=-2, емкость счетчика

cTii;)2Hiiii 1 = 2. Если бу LyT Hp2BH;Ibпо прш!яты на интервале стирания (qB) второй и пятый элементы комбинации и транса)ормироB3i1 на пнтерв3;Ip стира!Ння (Р,-) восьмой элемент, то после регистрации второго и пятого элеме:t ТО» счетчик стираний перс!!ол!!яется, за!к()ыгаст ключ и стира!(пе восьмого трансформ)!рсва-iHQI элемента не поступает в блок формирования .IiîëHIHîìOB ошибок. Однократная ошпока, обуслс!зленная восьмым элеменToм, не нснра!вляет я. Число различных варна г(ов о!Нпбок данног0 типа составляет

Оцс:-1!ка вероятностеи исправляемых од!Но5 крат!Ных и двухкрат!1Ых ошиоок для известного устройства, может быть выполнена по следующим формулам

" ="-,, p-.-1 --:--, "„С„, Р-,q,1 - !. (1)

Кроме того, иззест oe устройство имеет с; Ож:!ую конструкцшо, обусловленную нали:пем второго блс 2 обнаружения ошибок, 20 выходного накопителя, счетчика и кл!Оча.

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

3Т0 дсс!игаст я тем, что,з п)едлагаемом устройстве зыхо < дзухпороговой схемы сое25 дпнен с первь)м входом блока формирован!!я полиномов ошибок, второй вход которого соединен с вторым выходоi! Олока обнаружен!!я ошиоок,,Bbiход,сумматора по модулю дза соединен с Bxo/0)1 Олока 0023руже(!Ия Ош!1Оок.

В результате в е «стирания», фиксируемые двухпороговой схемой Взодятся в блок ()О))МIIPC!32!HIIH !!О,1!1 10МО 3 ОНIИООК, ITO 10330., ЯЕТ IICHP 3 BHTb B«Е OLU H ÎKII В 11PC LC.! с Х ООП 2, ) с ж ИЗ i!OLL! HX С . - 00:: «ГЕЙ КС 2, 3 2 !! - Ii 110 I C пнем ошибок, обу ловле: Ibtx тра!! фо)мац!! It

DHc иHTcp3 2 ë 2 cTIIО i .!1! я (1 ) ), i c)1 c:! 70в комбинации. Од:12ко к;) Iп-1ссT!!0 этп ollliiоок:.1:)жет быпгь сдела! о ":коль угî !I!0 маль)м:)2 с:."t с)Ы )Оj)3 ДОСТс1то .:! О!! ill lt ) Н .I bi ! Е,) ",;! 12 Стil") 2 ппя. В извест.шм у:гро!!Стзе это пр. 1:!ципиальHCK;IIOiI3CTClI, таК Кс!К C

HHTCCP l3 .I 3 CT i! 0;:,!1Я 3 ЗЕЛ II H IB3BTCH iI t С ло «стираний», а следователь!!о и число неп=правляемых ош!!бок за счег того, что не Все

«стирания» вводят.я в блок формирования

Г10ЛИ НОМ ОВ ОШИ OOI(П.) 3 2 П " !) СПО,! 11С-1 И Я СЧ Т чика стира!ний.

На черте)ке представлена фуш цпональная схема устройства для исправления ошибок в

КОДОВОЙ КОМОИН2ЦИИ.

Устройство содер)кит дзухпороговую схему 1, блок 2 формирования полиномов ошибок, блок ) обнаружения ошибок, однопоро55 говую схему 4, сумматор 0 по модулю дза, буферный 6 и основной 7 блоки памяти, элемент «И» 8, первый выход 9 и второй вы.д 1О.

Двухпорогозая схема 1 осуществляет зы50 явление ненадежных элементов («стираний») ь кодовой комбинации. Блок 2 формирования пол!!посмев Ошибек зоспри!нимает «стирания» и па иx о. !!Озс (рс )ми:)ует различные полиномы ош: бок, вкл)очающпе нулевой полином, поли! .омы с од!1: кратii-ь:м1. ошибками, полино526898!

S = — С, полином03.

t=o

t t

1,(Я. Г

i =-О i — — О мы с двух!крат?!ыми ошисками, гюлиномы с

l-кра7гныгми ошибками. Причем первым всегда фарми руется !нулевой полинам, а далее— полиномы ошибок в порядке убывания,вераятгнОстей их появле!Ния в иепользуемом канале связи. Так,,например, при работе в двоичгном симметричном стирающем канале без памяти, после нулевого .поли!нома формируются полиномы 0+IHoK!pBTIHblx ошибок, затем поли!номы двухкратных ошибок и та к далее, включая формирование полиномов f-кратных ошибок. Так как число «С7гира ний» r возможна в пгредглах от нуля до и, то для обеспечения наибольшей исправляющей способности блок формирования полиномов ошибок должен формировать

В каждом каггкретном слу гае Велич!!на S выбирается !а cc:!азалии неравенства П711 нcоаи3pу?кении Ошиакгl 3 Опрсде 7е11ном цик;!е проверки по сиг,:!алу из блока 8 об<наружег!ия ошибок в очередном ц.!клс блок

2 формирует полинам ошибки а !ялог:!ч,!ый п р еды,дущем у.

Блок 8 ооггаружсния ошибок ана !из;!ругт принимаемую кодовую комбигнацию и различныс вариа|нты исправляемых комбинаций на наличи или отсутствие ошибок. Сумматор 5 по моду.!!о два прел-133 !ачен для;наложения

Ii3 прав=ря мую комбинацию п07и номаз ошибск, фоатпугмых 6.70ка?, 2. Однопаро "QBBH с;сма 4 является регистпирующим хстройствам, реализующим, например, дискретно-интегральный метод приема сигналов. БуферIHbIH блок памяти 6 осуществляет накоплен. е э.!Сментсз очередной кодо вой комбинации 3 то время, как проверяется предыдущая комби.гяция. Емкость буферного блока памяти

О пледе,.!1!ется cKopocTbio хгадуляции пг" гдяBBP_#_b1?! iCoO6LIIC HIHH И CKOpOCTblo oápaáoTKH кодовой комбинации,в у" тройстзе. Основной

6 JI 0 K II 3 м H T H 7 II p P д, н 3 3 H 3 I е H g.. l H 3 3 I H C è II p H

Пятой комбигнации и выдачи ее да S раз HB обработку.

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

Принятая кодовая комбинация одновременно поступает на входы однопорогозой 4 и двухпорогoBQH 1 схе vI. С выходя од г ."Вoговой схемы 4 кодовая комбинация, состоящая из гас" гдсзатгльнсс7И «О» и «!».., з буферный блск памятг! 6 !!Водится г, 0::!Оз:.:Ой блок памяти 7. В рсзу:.ьтатс анал.!Bà кч?кдого пригнимаемаго элеме ITà кодовой ксмбинации HB Выходе дв? хпорагозой схс >гы 1 появляется сигнал «стирания» в том случае, если и!?инятый элг>гг-fT не co?KPT ábITb OTQ?KpccTB5

55 г.о

65,7cfH ни с «!» ни с «О». Эти ненадежныс элементы подаются в блок 2 формирования пали-!!Омов ошибок.

После приема l2 элгх!ентов комбинации корректирующего (n. /г) -,кода, последняя из основного блока памяти 7,подается на,вход сумматора 5 по модулю два, ня другой вход которого одновременно поступает нулевой полинам бла ка 2 формирования полиномов ошибок. С выхода сумматора 5 элементы комбинации, соответствующие принятой кодовой комбинации, подаются на,вход блока 8 обпаруже ния ошибок, На выход устройства элементы не поступают. Блок 8 обнаружения ошибок янялизиругт принятую комбинацию и при ига 6 на р ужении Ошиаки Выдает сигнал В блок 2 формирования поличомов ош;!бок и на второ!! вход элемента «И» 8, открывая его.

Блок 2, восприия3 сигнал необнаружения ошибки, B 0>IBpc7!Io>I цикле фар.>!Пруст IIQ!IHном ошибки, аналогичный предыдущему, т. е. нулезог!. Кодогзая комбинация второй раз по"т;.пает из о:нозного блока памяти 7 через сумматор 5:! открытый элемент «И» 8 непосредствс:-гио на выход устройства 10.

Если при г..:сзо;i цикле проверки блок 8 обна ружизаст ошибку, то комбинация из ocHîBHîãî блока памяти 7 выдается на проверку второй раз и г,ри этом блок 2 фозмирова.:Пя полиномав ошибок фармирусг полинам

ОДНОI" Р 3Tlloii ° 1>1.10КИ, 1" ОТ JPblli 113 С > ?f:>f BÒOPC

5 по модулю два осуществляет первог исправлг::;".с и; i!!Втой ко?164!Нации. Псправленка >10 1;1 i 11 1 i!. р ICTC51 6 70KO >I 8, KOTOрый при неабнар > жcHlill Ошибки зыдягт сиг:гал 3 бла,:; 2 и на 3 ора!", вход эл мента «Н» 8, открывая его. Блок 2. восприняв сигг!ял необнаруж 11ия ошибки, формирует полинам однократной ошибки, аналопгчны.": предыдущему, и исправлен!!ая комбинация в 0 !Среднам цикле через открытый элемгнт «II» 8 посту!пает на выхо"., у=тройства 10.

Если блок 8 сб?п.;руживягт ошибку в псрВ О м В ", D H Я!! Те и 3 11 р 3 B 7 P l i I!011 К 0 >1 6 П Н 11 ц и 1! >

IIpoBcpK1l г>рОда,.lж:1ются. П.>:! это?! 6?..гак 2 фоРхги)7Угт 0;PPP!,:10й Ilo,!!!i>!OAI o I, :13! Р;гтнай ошиаки и T"-.,K да г дo пгр >010 !гсобиаружения ошибки 3 каком-либо из вариантов исправлен.IOII кам0: гацпl. ИсправлcHíая комби|нация B очеред;!ом цикле работы через открытый элемент «II» 8 поступает на,выход устройства 10. Е.-ли ошибка будет обнаружеH3 IIipH B х цик !ах проверки, То блОк 8 oáHßр > жгния 0HliioOK фикси)?уеT ня;1ичие В принятой комбинации не:!Спразляемой ошиак;1, о

".гм выдаст си-. .ял на зыход 9, В системах с

ppøBþùpIi обp>ITC:ol! сзязгяа этот сигнал исПОЛЬЗУЕТСЯ Д,1Я ОТ» ЯНИЗЯ:гн.i 1. >PСCHPOC;1 Ñ

Слож.lа" I ь 73!<01!!P> гаи . !. >""! )301! "TB, В ОсНОВ:-10М, 0 10: и >Т 11 К0,1ИЧССТГ>ОМ ЭЛЕЪIЕНТОВ памяти, и -..бхад.::чых для ="0 ргали3àöèè. Пззестное угт?01." Яо гри использовании цикли<1< =кого (il, l2) — кода без учета блок 1 формирования полиномов ашиаок coдгр?кит "» раз526898

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

Р,,— 0,4 1Π— 2;

Р =-0,65.10

Р, = =0,15 10

P 1,310, )

7 l

I (Составитель B. Крь1аова

1»оррсктор 8. Гут Ië: гибааова Техреду Х Тараненко

3ска, 026)1221 IbZ. № 1673 Тиран< 864 Г1о: п .сп

111!И11гт".I Госуд", ствепного комитета Совета Министров СССР по делам изобретений и открь|тпй

Москва, )К-35, Раушская наб., и. 4/5

Тпп.

Предлагаемое устройство в частном случае может содержать и разрядов регистра сдвига.в буферном и основном блоках памяти (n — k) разрядо в в блоке об наружения ошибок, что соста вляет сг — — 2n — k разрядов.

Таким образом, предлагаемое устройство требует для овоей реализации, количество элементо в памяти на /г меньше, чем известное, где h = pI — p> = 4n — k.

Hip.и иепользов а ни и циклического (136, 120)- кода (ГОСТ 17422; PC2344 — 70) Й=424 разряда.

Оценим, степень увеличения исправляющей способности этого устройства по сравнению с известным для следующих исходных данных: длина кодовой комбинации n=10; кодовое ,раlсстоян1. Й=З; .величина порога и шири на

:интер вала стирания равны 2о, в связи с чем вероятность стирания правильно принятого элемента:комбинации q> =- 1,4. 10, вероятность стирания TipBliIсфо рмирoiBа нного элемента Рз= 2 . 10 - и верояпность правильного приема элемента комбинации q== 0,84. Подставляя исходные данные в выражения (1), (2), (3) и (4), получим

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

1300 однократных и 65 двухкрап1ых ошибок.

Предложснное устройство иап|равляет однократных ошибок на 150, а двухкратных яа

40 больше, чем из вестное устройство. При узеличзнии интенсивности помехи;В КBнале связи абсолюиное количество дополнительно иопразляемых ошибок з предлагаемом устрой стве увеличи вается.

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

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