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

(11) 443389 Союз Советских Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 61) Зависимое от авт. свидетельств 2) Заявлено 14.11,72 1) 1846196/1 51) л. С 061 11/10 Н 031 с 13(3 явкиприсоединение Государственный комите Совета Министров СССР по делам изобретенийи открытий(72) Авторы изобретения А. А. Давыдов и В. Б. Афанасьев Ордена Ленина институт проблем управления(54) КОДИРУЮЩЕЕ УСТРОЙСТВО ЛИНЕЙ КОРРЕКТИРУЮЩЕГО КОДА+(,:,=,) миа представляюш, асть т-го уравнени формируетсобой правую систем ь нием ко ь Благо ходом в ия знак ения укто жесления ше ль торои явля- даря включислитель, в предлаазанной сисамое обоправых чаИзобретение относится к области электронных дискретных устройств систем автоматики, телемеханики и вычислительной техники и предназначено для использования в системах передачи и хранения дискретной информации в качестве кодирующего устройства (т. е. устройства, вычисляющего контрольные символы) линейного корректирующего кода с основанием д. (Рассматривается случай, когда ц является нечетным простым числом). Кроме того, функциональные возможности устройства таковы, что оно может использоваться для вычисления синдрома и обнаружения ошибок в процессе декодирования. Известны кодирующие устройства линейных корректирующих кодов с нечетным простым основанием, содержащие блок управления, вентили, вычислительный блок, каждый разряд которого содержит сумматор по модулю основания кода и ячейку сдвига, вход которой соединен с выходом сумматора этого разряда, Первый вход сумматора каждого разряда, кроме сумматора младшего разряда, подключен к выходу ячейки сдвига предыдущего разряда.Недостатком известных устройств является то, что даже самые простые из них (в частности устройства для кодирования циклических кодов) содержат относительно большое количество д-х схем умножения, что существенно повышает затраты оборудования,В предлагаемом устройстве О-е умножителиотсутствуют. В результате количество обору дования в предлагаемом устройстве значительно меньше, чем в известных, причем выигрыш растет с увеличением основания О и с повышением корректирующей способности кода ,(т. е. с увеличением количества контрольных 10 символов), Так как выход ячейки сдвига каждого разряда вычислительного блока связан через вентиль со входом сумматора этого же разряда, то содержание каждой ячейки многократно складывается с поступающей в нее 15 информацией. В результате в ячейке сдвига1-го разряда многократно реализуется соотно- шение линейных уравнений, реются контрольные симвочению между выходом и вного блока, блока измененгаемом устройстве для решстемы можно использоватьрудование, что и для вычистей уравнения.На чертеже изображена блок-схема предлагаемого устройства.Оно содержит вычислительный блок 1, состоящий из з разрядов (з-й разряд является старшим, 1-й разряд - младшим, величина з совпадает с количеством контрольных символов и на единицу меньше кодового расстояния), сумматоры 2 - 2, по модулю д, ячейки 3, - 3, сдвига и вентили 4 - 45 - 7.Блок 8 изменения знака предназначен для получения числа (д - х) из д-го числа х, блок 9 управления - для формирования управляющих двоичных сигналов, (Этот блок в числе прочих элементов содержит генератор тактовых импульсов). Схема 10 сравнения с нулем предназначена для обнаружения ошибок в режиме декодирования путем сравнения синдрома с нулем,Тактовые входы всех ячеек сдвига, а также блок 8, связаны с выходом генератора тактовых импульсов (эти связи на чертеже не показаны),Работу устройства можно разбить на четыре этапа.На всех этапах сигналы, проходящие по показанным на чертеже цепям (за исключением двоичных управляющих сигналов, формируемых блоком 9), являются д-ми, т. е. каждый сигнал может принимать одно из значений: О, 1 (д - 1).Ячейки сдвига и вентили на всех этапах работы устройства функционируют следующим образом.При подаче тактового импульса ячейка 3; выдает хранящееся в ней д-е число на вход сумматора 2;+ (или на вход блока 8 при =в), а также на вход вентиля 2;, Одновременно эта ячейка запоминает д-е число, поступающее на ее вход с выхода сумматора 2. Каждый вентиль имеет управляющий двоичный вход (этот вход связан с выходом блока 9) и информационный д-й вход, На информационный вход может поступать одно из чисел О, 1, , (с 1 - 1). При наличии сигнала 1 на управляющем, входе вентиль открыт, и число, поступающее на информационный вход, проходит на выход вентиля. При наличии сигнала 0 на управляющем входе вентиль закрыт, и на его выход проходит число 0 независимо от сигнала на информационном входе.Перед началом работы все ячейки сдвига обнуляются, Для простоты при описании работы устройства з считается четным числом (при нечетном з устройство работает аналогично).На первом этапе работы устройства вентили 4 - 4, и 7 открыты, а вентили 5 и 6 закрыты. Через вентиль 7 д-е информационные символы аь а 2, , а (количество которых Й не должно превышать величины (д - з) ), начиная с символа ад, последовательно с частотойравной такту сдвига, поступают на вход сумматора 2 Каждый информационный символ может принимать одно из значений О, 1,(д - 1), После й-го такта сдвига первыйэтап работы закончен, В это время ячейка 3содержит сумму: а+а,+ +аьячейка 3 - сумму:5а+ а+, + а,ячейка 3, - сумму:10а + а++ а,Указанные суммы, как и все дальнейшие 15 суммы, приведенные при описании работыустройства, вычисляются по модулю д, т. е.каждая сумма может принимать одно из значений: О, 1 (ч - 1)На втором этапе работы устройства, который продолжается з тактов, вентили 4, 4, открыты, вентили 5 -закрыты. Работа устройства на этом этапе эквивалентна, работе на первом этапе в предположении, что на вход сумматора 2, поступают нулевые символы, К концу второго этапа ячейка 3, содержит сумму:А, =а, +а,++а,ячейка 3, - суммуА,=-. а, + а,++в+А - 135ячейка 3, - сумму:А - а+ а+ +д-.й - 1 ) Указанные суммы представляют собой взятые 45 со знаком-правые части линейных уравнений, решением системы которых являются контрольные символы.Третий этап работы устройства, на которомосуществляется вычисление контрольных сим О волов бь Ь 2, , Ьпродолжается з тактов.На протяжении всего этапа вентиль 5 открыт, а вентили 6, 7 и 4, закрыты, Вентили 4 - 4;закрыты на первом такте, а затем поочередно открываются, причем вентиль 4; открывается 55 на (+-1) -м такте и остается открытым доконца третьего этапа.Блок 8 устанавливается (с помощью блока9 управления) первым тактом третьего этапа в такое состояние, что при поступлении д-го 60 числа х на его информационный вход 11 онвыдает на выход число х для четного такта и число (д - х) для нечетного такта, считая от начала этапа. Так как в операциях по модулю д число (д - х) эквивалентно числу ( - х), то 65 на третьем этапе работы устройства через веи) 6,+А в ячейке Зр - сумма:- - ( )А в ячейке Зт+1 - сумма: в ячейке 3, - сумма: 35 60 65 тиль 5 на вход сумматора 21 последовательнопоступают числа; - А+ А; - ). А, - г- А +А,. В результате к концу третьего этапа в ячейке3, записана сумма:- Ь,= - ( - А,+А,+ - А, г+А),+Ь,= -- А,+ А, - А,+, - ( )А,в ячейке Зт (где т - четное) - сумма:- Ьт г 1 = -- Ат+г + Ат;.2 - ) - + А,Таким образом, нечетные контрольные символы получены со знаком- , а четные - со знаком +. Четвертый этап, на котором осуществляется выдача контрольных символов с одновременным присваиванием им правильного знака, продолжается з тактов. Вентили 41 - 4., 5 и 7 в течение всего этапа закрыты, вентиль 6 - открыт. Блок 8 устанавливается (с помощью блока 9) таким образом, что знак числа, поступающего на вход 11 в четном такте (считая от начала четвертого этапа), изменяется. Числа, поступающие на вход 11 в нечетном такте, проходят на выход блока 8 без изменения. В результате на выход устройства через вентиль 6 проходят контрольные символы: +К, +Ь , +Ьь Вычислены эти символы так, что равны нулю все суммы: г., = Ь, + Ь, + + Ь, + А з -- ) Ь,+ Ьз++1 2+ Ь,+А,С = Ь + Ьтг+, ,+ 10 15 20 25 30 40 45 50 55 Поэтому код, образованный из последовательностей, в которых контрольные символывычислены с помощью предлагаемого устройства, имеет кодовое расстояние (э+1) максимально возможное кодовое расстояние в линейном коде с з проверочными символами.Расстояние (я+1) позволяет исправлять -2ошибок или обнаруживать з ошибок.Работа устройства при использовании его впроцессе декодирования состоит из двух этапов, на каждом из которых регистр по-прежнему работает в режиме сдвига. Первый этаппродолжается (Й+з) тактов, в течение которых на вход устройства поступают последовательно символы аг), аг) , , а, Ь., Ь, ьЬг (штрих указывает, что некоторые изсимволов, возможно, искажены). Вентили41 - 4, и 7 открыты, вентили 5 и 6 закрыты.В,результате к концу первого этапа в ячейке3, записана сумма:гг: Ьг + 62 +) ., + Ь, + Аг)в ячейке Зт - сумма:пг - 1 з - 16)++ Ьх+ А,т - 1 т - 1в ячейке 3, - сумма:Ь,+А,(штрих у чисел А. указывает, что в их образовании участвовали слагаемые аь , аг.Набор сумм Ьь , 1., представляет собойсиндром, позволяющий обнаруживать ошибки,если они произошли, и исправить их.На втором этапе, который продолжается зтактов, происходит обнаружение ошибок путем сравнения компонентов синдрома с нулем. Вентили 4, - 4, и 7 закрыты, вентили 5и 6 открыты, блок 8 в течение всего этапа передает число без изменения знака. СуммыЕ. , г. проходят в схему 10 и одновременно перезаписываются в регистр. Если хотя быодна сумма Лт не равна нулю, то схема 10выдает сигнал обнаружена ошибка, Значения сумм Е, 1.ь сохраненные в регистре,являются исходными данными для исправления ошибок, которое должно осуществлятьсяспециальным устройством. Предмет изобретен и яКодирующее устройство линейного корректирующего кода, содержащее блок управления, вентили, вычислительный блок, каждый разряд которого содержит сумматор по модулю основания кода и ячейку сдвига, вход которой соединен с выходом сумматора этого разряда, а первый вход сумматора каждого443389 Составитель И. ХазоваТекред Т, Миронова Редактор Е. Семанова Корректор О, Тюрина Заказ 1103/3 Изд.1223 Тираж 624 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж, Раушская наб., д. 4/5Типография, пр. Сапунова, 2 разряда подключен к выходу ячейки сдвига предыдущего разряда, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит схему сравнения с нулем и блок изменения знака, информационный вход кото,рого подключен к выходу ячейки сдвига старшего разряда вычислительного блока, а второй вход подключен к первому выходу блока управления, другие выходы которого подключены к соответствующим вентилям, причем выход блока изменения знака через вентиль соединен с первым входом сумматора младшего разряда вычислительного блока и через 5 другой вентиль - с выходом устройства и сосхемой сравнения с нулем, ко второму входу су мматора каждого разряда вычислительного блока через соответствующий вентиль подключен выход ячейки сдвига того же разряда.