Кодирующее устройство линейного корректирующего кода

 

НИЕ

СПИ СА

ИЗОБРЕТЕНИЯ (ii) 443389

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Зависимое от авт. свидетельства (22) Заявлено 14.11,72 (21) 1846196/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 15.09.74. Бюллетень № 34

Дата опубликования описания 23.06.75 (51) М. Кл. С 06f 11/10

Н 03k 13!32

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

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

А. А. Давыдов и В. Б. Афанасьев

Ордена Ленина институт проблем управления (71) Заявитель (54) КОДИРУЮЩЕЕ УСТРОЙСТВО ЛИНЕЙНОГО

КОРРЕКТИРУЮЩЕГО КОДА

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

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

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

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

i-го разряда многократно реализуется соотношение и формируется сумма, представляющая собой правую часть i-ro уравнения системы линейных уравнений, решением которой являются контрольные символы. Благодаря вклю25 чению между выходом и входом вычислительного блока, блока изменения знака, в предлагаемом устройстве для решения указанной системы можно использовать то же самое оборудование, что и для вычисления правых ча30 стей уравнения.

443389

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

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

31 — 3, сдвига и вентили 41 — 4., 5 — 7.

Блок 8 изменения знака предназначен для получения числа (д — х) из q-ro числа х, блок

9 управления — для формирования управляющих двоичных сигналов. (Этот блок в числе прочих элементов содержит генератор тактовых импульсов). Схема 10 сравнения с нулем предназначена для обнаружения ошибок в режиме декодирования путем сравнения синдрома с нулем.

Тактовые входы всех ячеек сдвига, а также блок 8, связаны с выходом генератора тактовых импульсов (эти связи на чертеже не показаны), Работу устройства можно раз бить на четыре этапа.

На всех этапах сигналы, проходящие по показанным на чертеже цепям (за исключением двоичных управляющих сигналов, формируемых блоком 9), являются q-ми, т. е. каждый сигнал может принимать одно из значений: О, 1,..., (q — 1).

Ячейки сдвига и вентили на всех этапах ра боты устройства ф)ункционируют следующим образом.

При подаче тактового импульса ячейка 3„. выдает хранящееся в ней q-e:число на вход сумматора 2;+1 (или на вход блока 8 при

i=s), а также на вход вентиля 2;. Одновременно эта ячейка запоминает q-e число, поступающее на ее вход с выхода сумматора 2i.

Каждый вентиль имеет управляющий двоичный вход (этот вход связан с выходом блока

9) и информационный q-й вход. На информационный вход может поступать одно из чисел

О, 1, ..., (q — 1). При наличии сигнала «1» на управляющем, входе вентиль открыт, и число, поступающее на информационный вход, проходит на выход вентиля. При наличии сигнала «0» на управляющем входе вентиль закрыт, и на его выход проходит число «О» независимо от сигнала на информационном входе.

Перед началом работы все ячейки сдвига обнуляются. Для простоты при описании работы устройства s считается четным числом (при нечетном s устройство работает аналогично).

На первом этапе работы устройства вентили 4 — 4, и 7 открыты, а вентили 5 и 6 закрыты. Через вентиль 7 q-e информационные символы аь а2, ..., ад (количество которых k не должно превышать величины (q — з) ), начиная с символа ад, последовательно с частотой,,равной такту сдвига, поступают на вход сумматора 2ь Каждый информационный символ может принимать одно из значений О, 1, (q — 1). После k-ro такта сдвига первый этап работы закончен. В это время ячейка 3i содержит сумму: а +а2+,..., +ад, ячейка З вЂ” сумму:

5 а,+ а,+,...,+ a„ ячейка 3, — сумму:

10 а,+ a»+,...,+ а.

Указанные суммы, как и все дальнейшие

15 суммы, приведенные при описании работы устройства, вычисляются по модулю q, т. е. каждая сумма может принимать одно из значений: О, 1,..., (q — 1).

На втором этапе работы устройства, который продолжается sтактов,,вентили 4i 4, открыты, вентили 5 — 7 закрыты. Работа устройства на этом этапе эквивалентна, работе на первом этапе в предположении, что на вход сумматора 2> поступают нулевые символы.

К концу второго этапа ячейка 31 содержит сумму:

А, =а, +а,+,...,+ад, ячейка 32 — сумму

А,=- а, + а,+,...,+ в+А — 1

35 ячейка 3, — сумму:

А,= aa,+ aa,+,...,+ г+k — 1) Указанные суммы представляют собой взятые

45 со знаком « — » правые части линейных уравнений, решением системы которых являются контрольные символы.

Третий этап работы устройства, на котором осуществляется вычисление контрольных символов бь b2, ..., Ь„продолжается s тактов.

На протяжении всего этапа вентиль 5 открыт, а вентили 6, 7 и 4, закрыты. Вентили 4> — 4.- 1 закрыты на первом такте, а затем поочередно открываются, причем вентиль 4; открывается на (i+1) -м такте и остается открытым до конца третьего этапа.

Блок 8 устанавливается (с помощью блока

9 управления) первым тактом третьего этапа в такое состояние, что при поступлении q-го

60 числа х на его информационный вход 11 он выдает на выход число х для четного такта и число (q — х) для нечетного такта, считая от начала этапа. Так как в операциях по модулю

q число (q — х) эквивалентно числу (— х), то

65 на третьем этапе работы устройства через веи443389

+ Ь,+А,..., I

L,= b,+А,. в ячейке 32 — сумма: —,...,— ()А„ в ячейке 3,,+1 — сумма: в ячейке 3,— сумма:

65 тиль 5 на вход сумматора 2> последовательно поступают числа: — А„+ А, А.. — А,, +А,.

В результате к концу третьего этапа в ячейке

31 записана сумма: — b,= — (— А,+А,+,...,— А, г+А), +b,= — — А,+ А,— А,+,...,— — ()A„..., в ячейке 3 (где т — четное) — сумма:

+b = — А + А,„+г,— — bm l = — — А,г + i4m 2 —, —,...,+ А, Таким образом, нечетные контрольные символы получены со знаком « — », а четные — со знаком «+».

Четвертый этап, на котором осуществляется выдача контрольных символов с одновременным присваиванием им правильного знака, продолжается s тактов. Вентили 4> — 4., 5 и 7 в течение всего этапа закрыты, вентиль 6 — открыт. Блок 8 устанавливается (с помощью блока 9) таким образом, что знак числа, поступающего на вход 11 в четном такте (считая от начала четвертого этапа), изменяется.

Числа, поступающие на вход 11 в нечетном такте, проходят на выход блока 8 без изменения. В результате на выход устройства через вентиль 6 проходят контрольные символы:

+Ь., +Ь. 1 ..., +Ьь Вычислены эти символы так, что равны нулю все суммы:

L, =Ь, +Ь, +,..., + b,+À„

L ) Ь2+ ЬЗ+1 1+ 11 2

+ b,+А„..., L = b + bm +,...,+

Поэтому код, образованный из последовательностей, в которых контрольные символы вычислены с помощью предлагаемого устройства, имеет кодовое расстояние (s+1) максимально возможное кодовое расстояние в линейном коде с s проверочными символами.

Расстояние (s+1) позволяет исправлять—

2 ошибок или обнаруживать s ошибок.

Работа устройства при использовании его в процессе декодирования состоит из двух этапов, на каждом из которых регистр по-прежнему работает в режиме сдвига. Первый этап продолжается (k+s) тактов, в течение которых на вход устройства поступают последовательно символы а г„а г,, ..., а, b „b, ь

b (штрих указывает, что некоторые из символов, возможно, искажены) . Вентили

4> — 4, и 7 открыты, вентили 5 и 6 закрыты.

В,результате к концу первого этапа в ячейке

Зг записана сумма: гг = Ьг+ Ь2+,..., + Ь,, + Аг,..., в ячейке 3 — сумма: аг — 1 s — 1

Ь„, +,...,+ Ь,+А„„..., m — 1 m — 1 в ячейке 3. — сумма:

b,+À, (штрих у чисел А, указывает, что в их образовании участвовали слагаемые а ь ..., а г,).

Набор сумм L ь ..., L представляет собой синдром, позволяющий обнаруживать ошибки, если они произошли, и исправить их.

На втором этапе, который продолжается s тактов, происходит обнаружение ошибок путем сравнения компонентов синдрома с нулем. Вентили 4> — 4, и 7 закрыты, вентили 5 и 6 открыты, блок 8 в течение всего этапа передает число без изменения знака. Суммы

L „..., L g проходят в схему 10 и одновременно перезаписываются в регистр. Если хотя бы одна сумма L не равна нулю, то схема 10 выдает сигнал «обнаружена ошибка». Значения сумм L „, г ь сохраненные в регистре, являются исходными данными для исправления ошибок, которое должно осуществляться специальным устройством.

Предмет изобретен и я

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

443389

Составитель И. Хазова

Текред Т. Миронова

Редактор Е. Семанова

Корректор О. Тюрина

Заказ 1103/3 Изд. № 1223 Тираж 624 Подписное

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

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

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

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