Устройство для перестановочного декодирования циклических кодов Советский патент 1977 года по МПК H03M13/51 G06F11/10 H04L17/30 

1

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

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

Одно из известных устройств содержит многотактный линейный фильтр и селектор синдромов ошибок 1.

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

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

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

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

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

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

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

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

Блок-схема устройства для перестановочного декодирования циклических кодов представлена на чертеже.

Устройство для перестановочного декодирования циклических кодов содержит буферный блок 1 памяти, предназначенный для приема и запоминания поступающей из канала связи кодограммы, регистр 2 сдвига с управляемой

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

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

Принятая сигнальная кодограмма поступает на вход буферного блока 1 памяти, где происходит ее хранение. Далее с выхода буферного блока памяти через сумматор 7 ио модулю два кодограмму подают на вход регистра 2 сдвига с управляемой обратной связью. Первоначально при передаче принятой кодограммы на сумматоре 7 по модулю два проходящую кодограмму складывают с нулевой комбинацией ощибок, вырабатываемой генератором 6. По команде из блока 3 управления, образованный в регистре 2 сдвига с управляемой обратной связью, синдром одновременно подают в анализатор 4 количества ненулевых символов синдрома и анализатор 5 положения ненулевых символов синдрома.

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

аГо-1

(x)-Qj{x)l,.,)

(Qj(4) (1)

Ь{х)-принятая с искажениями

где кодограмма;

Qj()-предполагаемая комбинацию ошибок;

w b{x}-Qi(x)g(x) - вес (количество ненулевых символов) синдрома, образованного от деления многочлена Ь(х)-Qj(x) на полином g(x); do - кодовое расстояние кода: w(Q}(x))-вес (количество ненулевых символов) предполагаемой комбинации ошибок.

В анализаторе положения ненулевых символов синдрома проверяется выполнение условия того, что наличие нулевого промежутка s начале (в конце) синдрома длиной равной или большей нулевого промежутка, определенного из условия обеспечения передаваемой информапии, согласно выражению;

1 + 2 1 р a-iog,

+ 1. (2)

-ss

-РОШ («)з

где Q - нулевой промежуток в начале (в конце) образованного при декодировании синдрома;

Qs-нулевой промежуток, определенный из условия обеспечения заданных требований по верности передаваемой информации;

С/,- число сочетаний из k по t; k - информационная часть кодограммы; f - число ошибок, приходящихся на информационную часть кодограммы; бц - предельная кратность предполагаемой комб1:нации ошибок, цриходяшейся на информационную часть кодограм;.1ы;

п -длина кодограммы; р - вероятность искажения одиночного

символа в канале связи; а -показатель группирования ошибок; рош(«); ад-заданная вероятность необнаружения ошибок в принятой кодограмме.

Если ни одно условие не выполняется, то по команде из блока 3 управления находящийся в регистре 2 сдвига синдром начинает сдвигаться нри работающей обратной связи и для каждого таким образом получаемого синдрома (для каждого такта сдвига) проверяет выполнение указанных условий (1) и (2). Одновременно с синдромом в буферном блоке 1 иамяти циклически сдвигают иаходянгуюся там кодограмму. Если для таких процедур не удается выявить и исправить ошибку, то на генераторе 6 начинают вырабатывать различные предполагаемые комбинации ошибок, которые подают на сумматор 7 по модулю два для сложения с проходян1ей кодограммой перед ее декодированием. В том случае, если для одной из таким образом полученных кодограмм выполняется одно из указанных условий, то приступают к исправлению выявленных ошибок, для чего кодограмму, находящуюся к этому моменту времени в буферном блоке 1 памяти, выдают на сумматор 8 по модулю два. Сложением по модулю два этой кодограммы с последней комбинацией ошибок, зафиксированной в генераторе 6, исправляют независимые ошибки, а сложением с сиидромом, зафиксированным в регистре сдвига, - другую часть вектора ошибок, приходящуюся на ее проверочные символы. После указанных операций исправленную кодограмму записывают в буферный блок памяти, при этом она может отличаться от переданной только сдвигом. По команде из блока 3 управления проводят соответствующий циклический сдвиг кодограммы в буферном блоке памяти и затем принятое сообщение выдают корреспондеиту. Если ни

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

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

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

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

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

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

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

входом буферного блока памяти.

Источники информации, принятые во внимание при экспертизе:

1.Колесник В. Д., Мирончиков Е. Т. Декодирование циклических кодов. М., Связь, 1968,

с. 67, рис. 3.6.

2.Питерсон У. Коды, исправляющие ошибки. М., Мир., 1964, с. 212-219, рис. 10.1 (прототип).

Вкод

Выход