Кодирующее устройство линейного корректирующего кода Советский патент 1974 года по МПК H03M13/13 G06F11/10 

1

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

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

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

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

У-Г,

У

+

20

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

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

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

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

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

Работу устройства можно разбить на четыре этапа.

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

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

При подаче тактового импульса ячейка 3; выдает храняшееся в ней q- число на вход сумматора 2г+1 (или «а вход блока 8 при :s), а также на вход вентиля 2. Одновременно эта ячейка запоминает q-& число, поступаюшее на ее вход с выхода сумматора 2f. Каждый вентиль имеет управляющий двоичный вход (этот вход связан с выходом блока 9) и информационный q-vi вход. На информационный вход может поступать одно из чисел О, 1, ..., (). При наличии сигнала «1 на управляющем .входе вентиль открыт, и число, поступающее на информационный вход, проходит на выход вентиля. При наличии сигнала «О на управляющем входе вентиль закрыт, и на его выход проходит число «О независимо от сигнала на информационном входе.

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

Па первом этапе работы устройства вентили 4i-4s и 7 открыты, а вентили 5 и 6 закрыты. Через вентиль 7 q-Q информационные символы ui, az, ..., uh (количество которых k не должно превышать величины (q-s)), начиная с символа flft, последовательно с частотой, равной такту сдвига, поступают на вход сумматора 2. Каждый информационный символ может принимать одно из значений О, 1,

. . ., (q-1). После /г-го такта сдвига первый этап работы закончен. В это время ячейка 3j содержит сумму: ,..., +ah, ячейка 82 - сумму:

М I / 2 ,, //fe -1

l)+( + ( 1 )ячейка 3s - сумму:

S- 1 , / s ,/k-l

s-l)+(s-l)(s-lbУказанные суммы, как и все дальнейшие суммы, приведенные при описании работы устройства, вычисляются по модулю д, т. е. каждая сумма может принимать одно из значений: О, 1, . .., (q-1).

На втором этапе работы устройства, который продолжается s тактов, вентили открыты, вентили 5-7 закрыты. Работа устройства на этом этапе эквивалентна работе на первом этапе в предположении, что на вход сумматора 2i поступают пулевые символы. К концу второго этапа ячейка 3 содержит сумму:

Л, :ia,+ a.+,..., + aft, ячейка За - сумму:

Л,-().+( + ),.++

- г+,-).,

Указанные суммы представляют собой взятые

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

Третий этап работы устройства, на котором осуществляется вычисление контрольных символов bi, bz, . .., bs, продолжается s тактов. На протяжении всего этапа вентиль 5 открыт, а вентили 6, 7 и 4s закрыты. Вентили 4i-4s-i закрыты на первом такте, а затем поочередно открываются, причем вентиль 4,- открывается

на (г4-1)-м такте и остается открытым до конца третьего этала.

Блок 8 устанавливается (с помощью блока 9 управления) первым тактом третьего этапа в такое состояние, что при поступлении q-vo

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

на третьем этапе работы устройства через вентиль 5 на вход сумматора 2 последовательно поступают Числа: - А, + , ,, -А„ + А,.

В результате к концу третьего этапа в ячейке 3i записана сумма:

-Ь, - (-А, + 4 +, .,-As-i + А,), Б ячейке За - сумма:

+ й.,+ ()А,-(и.+,...,

S- 1

А ,. . . , 1

в ячейке 3т (где т -четное)-сумма:

. ,ffn -1 ;. , / m ,

+ ( iM-+ jAnfb m-ll т -

s-1

А„ т-I

В ячейке 3m4-i -сумма:

)А.,, + ()А. (т

bm+l - / tn I ,т Is - т

-,...,+

в ячейке 3s - сумма:

-

AS - Aj. + Ь,

- U-ij

Таким образом, нечетные контрольные символы получены со знаком «-, а четные - со знаком «4-.

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

L,b, + b,+,...,, + A,,

-()+(i)+-+

+ , + А„...,

i. + ( ,b.n...++

т

+ ( Ь,

т -1

/S-1

L,

Ь, +Л.S-1

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

Расстояние (s+1) позволяет исправлять -55 ошибок или обнаруживать s ошибок.

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

0 продолжается (/s+s) тактов, в течение которых на вход устройства поступают последовательно символы ah, ah-i, ..., al, bs, bs-i, . .., bi (штрих указывает, что некоторые из символов, возможно, искажены). Вентили

5 4i-4s и 7 открыты, вентили 5 и 6 закрыты. В .результате к концу первого этапа в ячейке 3i записана сумма:

LI - bl-Jf-b +,..., +bs- Ai,..., Q в ячейке 3m - сумма:

1„, b,n 4-+ ( M И+А,;,

т-))

в ячейке 3s - сумма: 5., s - 1

bs + A,

L,

(.

1

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

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

На втором этапе, который продолжается s тактов, происходит обнаружение ошибок путем сравнения компонентов синдрома с нулем. Вентили 4i-4s и 7 закрыты, вентили 5 и 6 открыты, блок 8 в течение всего этапа передает число без изменения знака. Суммы Ls, ..., Ll проходят в схему 10 и одновременно перезаписываются в регистр. Если хотя бы одна сумма Lm не равна нулю, то схема 10 выдает сигнал «обнаружена ошибка. Значения сумм Ls, .. ., Ll, сохраненные в регистре, являются исходны.ми данными для исправления ошибок, которое должно осуществляться специальным устройством.

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

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

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