Устройство для перестановочного декодирования циклических кодов
иц 5527I6
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Реслублмк (61) Дополнительное к авт. свид-ву (22) Заявлено 12.06.73 (21) 1933122/24 с присоединением заявки ¹ (23) Приоритет
Опубликовано 30.03.77. Бюллетень № 12
Дата опубликования описания 17.05.77 (51) М. Кл.- зН 041 1/10
G 06F 11/10
Государственный комитет
Совета Министров СССР (53) УДК 681.326.7 (088.8) по делам изобретений и открытий (72) Автор изобретения
А. M. Ситников (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕСТАНОВОЧНОГО ДЕКОДИРОВАНИЯ
ЦИКЛИЧЕСКИХ КОДОВ
Изобретение относится к области вычислительной техники и передачи цифровой информации и может быть применено в устройствах передачи дискретных данных.
Известны устройства для декодирования циклических кодов, построенные на основе применения кодовых фильтров.
Одно из известных устройств содержит многотактный линейный фильтр и селектор синдромов ошибок (1).
Работа устройства основана на образовании некоторого подмножества синдромов, соответствующего какому-либо характерному расположению ошибок. Задача построения этого устройства сводится к построению контрольного блока, способного вычислять синдромы циклически сдвигаемых последовательностей, и комбинационной задаче построения селектора, определяющего принадлежность синдрома к некоторому подмножеству. Если контрольный блок можно без особых трудностей построить на основе многотактного линейного фильтра, то при построении селектора возникают значительные трудности, так как сложность последнего в большой степени «зависит от характера и чйсла исправляемых ошибок, Сложность построения у этого устройства наблюдается ужа при исправлении независимых ошибок небольшой кратнОсти, что является его основным не. достатком.
Наиболее близкое по техническому решению к изобретению устройство для перестановочного декодирования циклических кодов содержит регистр сдвига с управляемой обратной связью, вход сдвига которого соединен с первым выходом блока управления, а выход— с первым входом первого сумматора по модулю два, буферный блок памяти, первые вход и выход которого являются соответственно вхо10 дом и выходом устройства, второй выход блока управления подключен к второму входу буферного блока памяти, а второй выход последнего — к второму входу первого сумматора по модулю два (2).
15 Данное устройство имеет такой недостаток, как неполное использование информации о возникших в канале связи ошибках, которую можно получить из образуемого при декодировании синдрома. В известном устройстве ис20 пользуется только информация о положении ненулевых символов синдрома.
Цель изобретения — увеличение количества исправляемых комбинаций ошибок при неизменных временных затратах.
25 Это достигается тем, что в устройство вве. дены анализатор количества ненулевых символов синдрома, анализатор положения иену. левых символов синдрома, генератор предполагаемых ошибок и второй сумматор по мо30 дулю два. Третий выход буферного блока па552716 мяти соединен с третьим входом буферного блока памяти, четвертый выход буферного блока памяти — с первым входом второго сумматора по модулю два, второй вход которого связан с первым выходом генератора предполагаемых ошибок, а выход — с информационным входом регистра сдвига с управляемой обратной связью. Разрядные выходы регистра сдвига с управляемой обратной связью соединены с входамп анализатора положения ненулевых символов синдрома и анализатора количества ненулевых символов синдрома, выходы которых подключены к первому и второму входам блока управления, третий выход блока управления — с входом генератора предполагаемых ошибок, второй выход которого соединен с третьим входом первого сумматора по модулю два, а выход первого сумматора по модулю два — с четвертым входом буферного блока памяти.
Признаком того, что пакет ошибок совпадает с младшими разрядами синдрома является образование в процессе декодирования такого синдрома, у которого заранее определенное число старших разрядов равно нулю. Информация о количестве ненулевых символов синдрома в известном устройстве не используется, хотя для циклических кодов по ней можно получить достоверные данные о широком классе независимых ошибок (о их количестве и расположении). Признаком того, что полученный синдром соответствует независимой ошибке, является число его ненулевых символов, не превосходящее корректирующую способность используемого кода за вычетом кратности прибавляемой (испытываемой) комбинации ошибок.
Кроме того, если факт совпадения пакета ошибок с некоторыми разрядами синдрома устанавливать не по равенству нулю определенного числа старших разрядов синдрома, а по образованию на синдроме пакета ошибок длиной, меньшей или равной заранее определенной для используемого кода, то можно также повысить быстродействие декодирующего устройства.
Исходя из сказанного, предлагаемое устройство перестановочного декодирования циклических кодов позволяет более полно использовать информацию о возникших ошибках по образуемому в процессе декодирования синдрому. Последнее обеспечивает исправление одновременно пакетных, независимых, а также их некоторых комбинаций ошибок, что значительно увеличивает общее количество исправляемых комбинаций ошибок при неизменности временных затрат на декодирование.
Блок-схема устройства для перестановочного декодирования циклических кодов представлена на чертеже.
Устройство для перестановочного декодирования циклических кодов содержит буферный блок 1 памяти, предназначенный для приема и запоминания поступающей из канала связи кодограммы, регистр 2 сдвига с управляемой обратной связью, служащий для получения синдрома, соответствующего возникшим в канале связи ошибкам, блок 3 управления, осуществляющий управление всем процессом декодирования, анализатор 4 количества ненулевых символов синдрома, анализатор 5 поло. жения ненулевых символов синдрома, генератор 6 предполагаемых ошибок для формирования независимых ошибок небольшой кратности, приходящихся на информационную часть кодограммы, сумматоры 7, 8 по модулю два.
Работает устройство следующим образом.
Принятая сигнальная кодограмма поступа15 ет на вход буферного блока 1 памяти, где происходит ее хранение. Далее с выхода буферного блока памяти через сумматор 7 по модулю два кодограмму подают на вход регистра 2 сдвига с управляемой обратной связью.
20 Первоначально при передаче принятой кодограммы на сумматоре 7 по модулю два проходящую кодограмму складывают с нулевой комбинацией ошибок, вырабатываемой генератором б. По команде из блока 3 управления, 25 образованный в регистре 2 сдвига с управляемой обратной связью, синдром одновременно подают в анализатор 4 количества ненулевых символов синдрома и анализатор 5 положения ненулевых символов синдрома.
З0 В анализаторе 4 проверяется выполнение условия того, что количество ненулевых символов синдрома меньше или равно количеству исправляемых кодом ошибок за вычетом числа символов, образующих предполагаемые
35 комбинации ошибок, согласно выражению о (Ь (х) — Я, (х)),, <,) (— со (Q, (4) (1) Ь(х) — принятая с искажениями кодогра м ма;
Я, (х) — предполагаемая комбинацию ошибок;
z (6 (х) — Q; (х) )@,з — вес (количество ненулевых символов) синдрома, образованного от деления многочлена (Ь (х) — Q; (х) ) на полином а (х); с4 — кодовое расстояние кода:
ы (Q; (х) ) — вес (количество ненулевых символов) предполагаемой комбинации ошибок. где
+ 1, (2) В анализаторе положения ненулевых символов синдрома проверяется выполнение условия того, что наличие нулевого промежутка в начале (в конце) синдрома длиной равной или большей нулевого промежутка, определенного г0 из условия обеспечения передав".åìîé информьнии, согласно выражению:
552716 где Q — нулевой промежуток в начале (в конце) образованного при декодировании синдрома;
Q,,— нулевой промежуток, определенный из условия обеспечения заданных требований по верности передаваемой информации;
Cr, — число сочетаний из k по i;
/г — информационная часть кодограммы; число ошибок, приходящихся на информационную часть кодограммы; е„— предельная кратность предполагаемой комбинации ошибок, приходящейся на информационную часть кодограм;„ы;
n — длина ко .ограммы; р — вероятность искажения одиночного символа в канале связи; а †показате группирования ошибок; (poru(<))зад заданная Вероятность неоонаружения ошибок в принятой кодограмме.
Если ни одно условие не выполняется, то по команде из блока 3 управления находящийся в регистре 2 сдвига синдром начинает сдвигаться при работающей обратной связи и для каждого таким образом получаемого синдрома (для каждого такта сдвига) проверяет выполнение указанных условий (1) и (2). Одновременно с синдромом в буферном блоке 1 памяти циклически сдвигают находящуюся там кодограмму. Если для таких процедур не удается выявить и исправить ошибку, то на генераторе 6 начинают вырабатывать различные предполагаемые комбинации ошибок, которые подают на сумматор 7 по модулю два для сложения с проходящей кодограммой перед ее декодированием. В том случае, если для одной из таким образом полученных кодограмм выполняется одно из указанных условий, то приступают к исправлению выявленных ошибок, для чего кодограмму, находящуюся к этому моменту времени в буферном блоке 1 памяти, выдают на сумматор 8 по модулю два. Сложением по модулю два этой кодограммы с последней комбинацией ошибок, зафиксированной в генераторе б, исправляют независимые ошибки, а сложением с синдромом, зафиксированным в регистре сдвига, — другую часть вектора ошибок, приходящуюся на ее проверочные символы. После указанных операций исправленную кодограмму записывают в буферный блок памяти, при этом она может отличаться от переданной только сдвигом, По команде из блока 3 управления проводят соответствующий циклический сдвиг кодограммы в буферном блоке памяти и затем принятое сообщение выдают корреспонденту. Если ни
Зо
50 для одной из кодограмм, образуемой при декодировании, ни одно из указанных условий не выполняются, то это означает, что произошла ошибка, некорректпруемая выбранным кодом. В этом случае принятая кодограмма в буферном блоке памяти стирается и сообщение корреспонденту не выдается.
Формула изобретения
Устройство для перестановочного декодирования циклических кодов, содержащее регистр сдвига с управляемой обратной связью, вход сдвига которого соединен с первым выходом блока управления, а выход — с первым входом первого сумматора по модулю два, буферный блок памяти, первые ьход и выход которого являются соответственно входом и выходом устройства, второй вход буферного блока памяти соединен с вторым выходом блока управления, второй выход буферного блока памяти соединен с вторым входом первого сумматора по модулю два, о т л и ч а ющ е е с я тем, что, с целью увеличения количества исправляемых комбинаций ошибок при неизменных временных затратах, в устройство введены анализатор количества ненулевых символов синдрома, анализатор положения ненулевых символов синдрома, генератор предполагаемых ошибок и второй сумматор по модулю два, причем третий выход буферного блока памяти соединен с третьим входом буферного блока памяти, четвертый выход буферного блока памяти соединен с первым входом второго сумматора по модулю два, второй вход которого соединен с первым выходом генератора предполагаемых ошибок, а выход— с ип<рормационным входом регистра сдвига с управляемой обратной связью, разрядные выходы рс истра сдвига с управляемой обратной связью соединены с входами анализатора положения ненулевых символов синдрома и анализатора количества ненулевых символов синдрома, гыходы KQTopblx соединены с первым и вторым входами блока управления, третий выхо j блока управления соединен с входом генератора предполагаемых ошибок, второй выход которого соединен с третьим входом первого сумматора по модулю два, выход первого сумматора по модулю два соединен с четвертым входом буферного блока памяти.
Источники информации, принятые во внимание при экспертизе:
1. Колесник В. Д., Мирончиков Е. Т, Декодирование циклических кодов. М., Связь, 1968, с. 67, рис. 3.6.
2. Питерсон У. Коды, исправляющие ошибки. М., Мир., 1964, с. 212 — 2!9, рис. 10.1 (прототип).
552716
Составитель В. Крылова
Техред И. Карандашова
Редактор И. Грузова
Корректор Л. Орлова
Типография, пр. Сапунова, 2
Заказ 976/2 Изд. М 378 Тираж 869 Подписное
ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4!5
