Устройство для исправления одиночных ошибок интерполяционного кода

 

Изобретение относится к вычислительной технике. Его использование в системах передачи и хранения информации позволяет расширить область применения для случая, когда информационные символы кода являются элементами произвольного поля GF(g). Устрой- , ство содержит два сумматора, К-1 блоков перемножения и блок постоянной памяти (здесь К - количество информационных символов кода). Введение двух вычитателей, двух коммутаторов, демультиплексора и группы из К сумматоров обеспечивает работоспособность устройства как в случае, когда , так и в случае g Р , где Р - простое число, т 1,2,.,. 1 ил. 1 табл.

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

СОЦИАлйСТИЧЕСНИХ

РЕСПУБЛИК (59 4 С 06 F 11/08

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3906744/24 — 24 (22) 04.06.85 (46) 23.12.86. Бюл. Р 47 (72) С.Н.Хлевной (53) 68 1.326.7(088.8) (56) Авторское свидетельство СССР

Р 542194, кл. Н 04 L 1/10, 1977.

Авторское свидетельство СССР

Ф 894711, кл, G 06 F 11/08, 29.12.79. (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОДИНОЧНЫХ ОШИБОК ИНТЕРПОЛЯЦИОННОГО КОДА (57) Изобретение относится к вычислительной технике. Его использование в системах передачи и хранения информа.„ЯО„„1278 2 А ции позволяет расширить область применения для случая, когда информационные символы кода являются элементами произвольного поля GF(8). Устрой- . ство содержит два сумматора, К-1 блоков перемножения и блок постоянной памяти (здесь K — количество информационных символов кода). Введение двух вычитателей, двух коммутаторов, демультиплексора и группы из К сумматоров обеспечивает работоспособность устройства как в случае, когда 8=Р, ITl так и в случае g = P, где P — простое число, m = 1,2,... 1 ил. 1 табл.

52 2 5(„)- О, то на первом и третьем

5(«+1) выходах — нули, а на втором выходе

ы-

IX

1 12788

Изобретение относится к вычислительной технике и может быть использовано в системах передачи и хране— При э(», 1ф О и E„(О ния информации, представленной ин- на первом и втором выходах нули, а терполяционными кодами. на третьем выходе величина кода оп

Цель изобретения — расширение об- ределена как (8), ласти применения для случая, когда Для К = 3 и g =- 3 зависимость в информационные символы кода являют- ходных значений блока 10 от входнь ся элементами произвольного поля значений 1 и 1э,. (выходные значе

GF(g). ния вычитателей 5 и б соответствег

На чертеже приведена блок-схема но) показана в таблице. устройства.

Устройство для исправления одиночных ошибок интерполяционного ко15 да содержит первый 1 и второй 2 сумматоры, блоки 3 перемножения, группу сумматоров 4, первый 5 и второй б вычитатели, демультиплексор 7, О 0 первый 8 и второй 9 коммутаторы, блок 10 постоянной памяти, входы 11 0 1 0

1 и выходы 12.

Сумматоры 1, 2 и 4 и вычитатели О 2 О 1 О

5 и 6 выполняют свои операции по моK дулю g в общем случае g ф 2, К = 1 О 1 О

1,2,... Блоки 3 служат для умно—

25 жения соответствующего информацион- О 0 ного символа а„на величину j jE (2,К (IIIo модулю g. Блоки 1 4 могут быть О 2 выполнены на программируемых постоянных запоминающих устройствах (ППЗУ).з

Если на входах управления коммутаторов 8 и 9 присутствует потенциал логической "1", то значение кода на выходах коммутаторов 8 и 9 сост- 2 2 О О 1 ветствует значению кода на выходе 35 .соответствующего нычитателя 5 и б в противном случае — значению кода (К + 1)-м входе 11 для коммутатора 8 и (К+2)-м вхоце для коммутатора 9, 40

Если на входе управления демультиплексора 7 присутствует код числа О, то значения кодов на всех егo BIIxo

Определим избыточные символы дах также равны О. Если значение кода на входе управления демультиплек- (1) сора 7 равно 1, то входное значение демультиплексора;.. 7 будет подано на вход первого сумматора 4 группы и а „ т.д. вплоть до значения кода К на управляющем входе демультиплексора

Выход блока 10

Первыи Второи Третин

0 О О

О

1 1

1 2 . 0

2 О 1 О О

2 1 0 О 2

В основе работы устройства лежат следующие соотношения.

Зададим последовательность информационных символо» а,, а,. ° .„а, а; E GF(g), Ы(1,Kj, К c p.. х а„„, == Kia;

1= 1 (2) Локаторы избыточного кода определим как

Блок 10 постоянной памяти выполнен также на ППЗУ, причем, если L <„,„)=О и 2 (= 0 то на всех третьих выхо- 55

5 («+2) дах блока 10 — нули. Если 1 . („„1= О, а а 2 (Ф О, то на втором и третьем э(« выходах блока 10 — нули, а на пер-вом выходе — единица. Если 11 „„1j О

« 1 « 11 а а к «+2 а а (3) (4) где а„„ и а, — символы, сформированные из принятых символов а,.. .,а„

2 278852 с использованием (. ) стненно.

Пусть искажен j é и величина искажения и (2} соотнет

l симВОл ) E - (1 р К) равна а ),т.е. а = а; +Ajar, j 6(1,К), (5) Локаторы и (примут вид

Р (к.,) з(к > )

j1 - k K +

= - а;-j(a; ° ь )-Kia; 2 ia, 1=) Н i"-!

= -j j . (6)

>=I к к + + 5(. > )

)ч 15

Из (6) и (7) следует, что

+ (8)

5(К+2)

Видно, aего opgvva aj gE(1,Ê) 7 („,) ф О

7з(к, ) ф О. Таким образом, при иска е— нии. любого информационного символа, вычислив (8), определим номер искаженного символа. Вычисление (7) определит величину искажения (- Ь вЂ”

) поправка, которую необходимо прибавить к а чтобы получить истинное

) У

его значение).

Ф

Пусть при приеме искаженного а„,, 30

К 1 тогда Хц(к+,) = I "ix+il> " О, 2 (к+,)= О, т,е. вновь исчисленное значение а„„ является верным. Аналогично для а

Êt2 исчисленное а „, является верным, т.е. 2з(к+,)= О, 1„,(к, ) >- О.

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

Коды информационных символов а„, а с входов 11 поступают на 40 входы сумматора 2, на выходе которого образуется а„ (2), а также на

К3 2 входы блоков 3, результат умно>кения в которых суммируется совместно с а1 сумматором 1, на выходе которого об- 45 разуется а Ä (1). На выходах вычитателей 5 и 6 образуются локаторы

2Г(к„,)и 15(к, ) соответственно

Если принимаемое сообщение не искажено, т е 4з(кн) = О и iq(t2)= О, 50 то на всех выходах блока 10 присутст— нуют коды числа íуль нули будут и на управляющих входах сумматоров 4, вследствие чего их выходные значения соответствуют значениям последовательности а,...,. а„. Значения кодов на выходах коммутаторов 8 и 9 соответствуют значениям кодов ак и а „+ на соответствующих входах 11, При йскажении любого информационного символа локатор 2з((выход5(кф2) ное значение вычитателя 6) определяет величину поправки -hj . Номер искаженного символа (j E(1,К) ) определен на выходе блока 10. Вследствие этого демультиплексором 7 подана на j --й сумматор 4 величина попранки, которая скомпенсирует искажение j-ro символа.

Если искажен один из контрольных символов, то коды символов а,... а „ сумматорами 4 не изменяются, а один из коммутаторов 8 или 9 подключает к соответствующим выходам

12 выход нычитателя 5 или 6 в зависимости от того, какое из контрольных оснований искажено.

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

GF(g). В этом случае g может быть

Tll как простым числом Р, так и P где

m = 1,2,3. ° .

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

Устройство для исправления одиночных ошибок интерполяционного кода, содержащее К-1 блоков перемно>кения, где К вЂ” количество информационных символов кода, первый и второй сумматоры и блок постоянной памяти, выходы каждого i†- го (iE (1,К1) блока перемножения соединены с соответствующими (i+1) ми входами первого сумматора, входы каждого i-го блока перемножения являются соответствующими (i+1) — ми нходами устройства о т л иЭ ч а ю щ е е с я тем, что, с целью расширения области применения для случая, когда информационные символы кода являются элементами произвольного поля GF(g) в него введены первый и второй вычитатели, первый и второй коммутаторы, демультиплексор и группа из К сумматоров, первый входы первого сумматора группы объединены с соответствующими первыми входами первого и второго сумматоров и являются первыми входами устройства, входы каждого i-ro из остальных сумматоров группы объединены с соответствующими -ми входами второго сумматора и входами (i-1)-го блока пере

1278852

Составитель О,Ревинский

Редактор Н.Тупица Техред Б. Кадар Корректор Л.Пилипенко

Заказ 6839/47 Тираж б71 Подписное

ВНИИПИ Государствеш|ого комитета СССР по делам изобретений и открытий

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 множения, выходы первого и второго сумматоров подключены к вычитающим входам соответствующих вычитателей, суммирующие входы которых объединены с первыми входами соответствующих коммутаторов и являются соответственно (K+1)-ми и (К+2) -ми входами устройства, выходы первого вычитателя подключены к вторым входам первого коммутатора и первым входам блока 10 постоянной памяти, выходы второго вычитателя подключены к информационным входам демультиплексора и соотнетствующим вторым входам второго коммутатора и блока постоянной памя.ти, первый и второй выходы которого соединены с управляющими входами соответствующих коммутаторов, третьи выходы подключены к управляющим вхо" дам демультипле