Устройство кодирования-декодирования информации

 

Изобретение относится к технике связи и может использоваться в аппаратуре передачи данных для осуществления помехоустойчивого кодирования информации каскадным кодом. Технический результат - повышение помехоустойчивости передачи информации. Устройство содержит блок ввода-вывода 1, общую шину 2, блок памяти 3, первый, второй и третий буферные регистры 4,5 и 6, первый и второй узлы задержки 7 и 8, умножитель 9, коммутатор 10, блок сумматоров по модулю два 11, первый, второй и третий блоки ключей 12,13 и 14, первый, второй и третий элементы ИЛИ 15,16 и 17, последовательный информационный вход-выход 18, тактовый вход 19, пусковой вход 20, параллельные информационные входы-выходы 21, управляющие входы-выходы 22. 19 ил.

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

Известны устройства для кодирования [1] и декодирования [2, 3, 4] информации с использованием недвоичных кодов, например кодов Рида-Соломона.

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

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

Наиболее близким к предлагаемому техническому решению и выбранным вследствие этого за прототип является устройство кодирования-декодирования информации [5]. Устройство содержит блок ввода-вывода, выходы которого через первый блок памяти подключены к первым входам блока ввода-вывода. Выходы первого блока памяти через последовательно соединенные первый блок сумматоров, второй блок постоянной памяти и второй блок сумматоров подключены к вторым входам блока ввода-вывода. Блок ввода-вывода содержит микроЭВМ, подключенную через один межмодульный интерфейс к последовательно-параллельному интерфейсу, вход-выход которого является последовательным входом-выходом блока ввода-вывода, а через другой межмодульный интерфейс к параллельному интерфейсу, параллельные входы-выходы которого являются параллельными входами-выходами блока ввода-вывода.

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

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

Таким образом, кодирование и декодирование информации в известном устройстве осуществляется табличным способом. Число комбинаций, которое необходимо хранить в первом блоке памяти, равно 2^k, где k - число информационных разрядов в кодовой комбинации, а во втором блоке памяти - 2^r, где r - число проверочных символов. Известное устройство не может работать с большими длинами кодов, так как с ростом k и (или) r объем памяти составит N_зу = 2^k+2^r слов, что существенно усложняет и делает ненадежным устройство.

Практически величины k и r ограничены разрядностью микропроцессоров. Большинство эксплуатируемых в настоящее время микропроцессоров имеют разрядность, равную 16-32. Для помехоустойчивой передачи информации по каналам связи плохого качества, особенно с группированием ошибок, такой разрядности кодовых комбинаций явно недостаточно.

Повышения помехоустойчивости передачи информации можно достичь путем использования длинных кодов, имеющих приемлемую сложность реализации, например кодов БЧХ в поле GF (2^m), у которых длина кодовых комбинаций в пересчете на двоичные символы может составлять несколько тысяч или даже десятков тысяч. Примеры выполнения устройств кодирования-декодирования в недвоичных полях аппаратным способом приведены в [1, 2, 3, 4]. Их недостаток заключается в сложности реализации и фиксированности структуры.

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

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

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

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

Предлагаемое устройство обеспечивает кодирование информации каскадным кодом [6, с. 228], состоящим из двух кодов, внутреннего (n, k) и внешнего (N, K), где n и N - общее число, а k и K - число информационных символов в комбинации внутреннего и внешнего кодов соответственно.

В качестве внутреннего кода используются двоичные короткие коды, в качестве внешнего кода - недвоичные коды, например коды Рида-Соломона (РС) над полем GF (2^m), где m - расширение двоичного поля.

В качестве примера в предлагаемом устройстве использован внутренний (24, 16) код с образующим многочленом g(X) = x⁸ + x⁷ + x⁴ + 1, (1) исправляющий однократные ошибки, обнаруживающий все двукратные ошибки более высокой кратности.

В качестве внешнего кода используется код РС (241, 225) над полем GF(2⁸) с образующим многочленом поля F(X) = x⁸ + x⁴ + x³ + x² + 1 (2) с примитивным элементом поля α = 00000010.

Образующий многочлен кода РС имеет вид На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 - функциональная схема блока ввода-вывода 1; на фиг. 3 - функциональная схема дешифратора 25 (пример); на фиг. 4 - функциональная схема параллельного порта ввода-вывода 24 (пример); на фиг. 5 - функциональная схема последовательного порта ввода-вывода 26 (пример); на фиг. 6 - функциональная схема микропроцессорного блока 23 (пример); на фиг. 7 показано распределение области кодирования ОЗУ (пример); на фиг. 8 изображена блок-схема алгоритма кодирования информации внешним кодом (пример); на фиг. 9 - блок-схема алгоритма кодирования информации внутренним кодом (пример); на фиг. 10 дано схематичное представление распределения ячеек ОЗУ для записи информации, принимаемой из канала связи (пример); на фиг. 11 представлена блок-схема алгоритма декодирования информации, закодированной внутренним кодом (пример); на фиг. 12 - блок-схема обобщенного алгоритма декодирования внешнего кода; на фиг. 13 - блок-схема алгоритма вычисления коэффициентов синдромного многочлена (пример); на фиг. 14 показаны временные диаграммы управляющих сигналов; на фиг. 15 изображена блок-схема алгоритма определения коэффициентов многочлена локаторов стираний (пример); на фиг. 16 - диаграмма состояний; на фиг. 17 - структура массива коэффициентов многочлена локаторов стираний; на фиг. 18 - блок-схема алгоритма определения коэффициентов модифицированного синдромного многочлена (пример); на фиг. 19 - блок-схема алгоритма определения коэффициентов многочлена локаторов ошибок (пример).

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

Основное отличие предлагаемого устройства от прототипа заключается в обеспечении операций кодирования и декодирования информации в поле GF(2^m), для чего в состав устройства введены блоки, осуществляющие под управлением микропроцессора операции в этом поле.

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

Так, например, при вычислении коэффициентов S_m синдромного многочлена по формуле Горнера [7, с. 175] где , R - число проверочных символов кода PC;
- символы принятой кодовой комбинации;
α - примитивный элемент поля GF(2^m);
N - длина кодовой комбинации кода PC,
элемент α записывается в первый буферный регистр, символ C₁ - во второй буферный регистр, а последующие символы - в третий буферный регистр, при этом результат вычисления получается сразу же при вводе символа C_j во втором буферном регистре. Благодаря такой организации вычисления наиболее сложная операция определения коэффициентов S_m осуществляется достаточно быстро.

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

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

По сравнению с другими техническими решениями, реализующими кодирование и декодирование информации в поле GF(2^m), предлагаемое устройство является более простым. В самом деле аппаратная часть предлагаемого устройства, используемая для операций в поле GF(2^m), содержит три буферных регистра, умножитель, коммутатор, блок сумматоров по модулю два, две схемы задержки, три ключа и три элемента ИЛИ.

В устройстве кодирования [1] кроме других узлов содержится N-K формирователей проверочных символов, каждый из которых соизмерим по объему с аппаратной частью предлагаемого устройства.

В устройстве для декодирования кода Рида-Соломона [2] только для операции вычисления синдромов блоком проверок требуется N-K секций, каждая из которых содержит три умножителя, четыре блока сумматоров, осуществляющих операции в поле GF(2^m), генератор элементов поля GF(2^m), регистр, т.е. по объему больше, чем аппаратная часть предлагаемого устройства, используемая для этих целей. При этом следует учесть, что в [2] блоки вычисления многочлена локаторов стираний и блок решения ключевого уравнения являются соизмеримыми с блоком вычисления многочлена обобщенных проверок.

Набор вычислительных операций в поле Галуа GF(2^m), реализуемый в [4], обладает низкими функциональными возможностями, требует многотактных схем управления. Устройство выполняет сумму только двух произведений, и с помощью его затруднительно выполнить вычисления по формуле (1).

Анализ этих и других технических решений [3] показывает, что, как правило, процедура декодирования кода PC выполняется набором узлов, каждый из которых выполняет какую-либо одну операцию при общем их числе порядка 10 (см. далее обобщенный алгоритм декодирования, фиг. 12). Предлагаемое устройство небольшим набором аппаратных узлов и микропроцессором выполняет все эти операции, что и позволяет достичь технического результата: обеспечение кодирования и декодирования информации длинными кодами в поле GF(2^m).

На фиг. 1 представлена функциональная схема предлагаемого устройства. Устройство содержит блок ввода-вывода 1, общую шину 2, блок памяти 3, первый 4, второй 5 и третий 6 буферные регистры, первый 7 и второй 8 узлы задержки, умножитель 9, коммутатор 10, блок сумматоров по модулю два 11, первый 12, второй 13 и третий 14 блоки ключей, первый 15, второй 16 и третий 17 элементы ИЛИ, последовательный информационный вход-выход 18, тактовый вход 19, пусковой вход 20, параллельные информационные входы-выходы 21, управляющие входы-выходы 22.

Устройство имеет следующие связи. Входы-выходы блока ввода-вывода 1, блока памяти 3, информационные входы первого буферного регистра 4, первые входы коммутатора 10 и выходы первого 12, второго 13 и третьего 14 блоков ключей соединены с общей шиной 2. Выходы первого буферного регистра 4 через умножитель 9 подключены к входам первого блока 12 ключей и к первым входам блока сумматоров по модулю два 11. Выходы коммутатора 10 через второй буферный регистр 5 соединены с вторыми входами умножителя 9 и с входами второго блока 13 ключей, а через третий буферный регистр 6 - с входами третьего блока ключей и вторыми входами блока сумматоров по модулю два 11, выходы которого соединены с вторыми входами коммутатора. Первый Q1, второй Q2 и третий Q3 управляющие выходы блока ввода-вывода 1 подключены соответственно к управляющим входам первого 12, второго 13 и третьего 14 блоков ключей, четвертый Q4 - к входу записи первого буферного регистра 4, пятый Q5 - через первый элемент ИЛИ 15 к входу записи второго буферного регистра 5, через третий элемент ИЛИ 17 к управляющему входу коммутатора 10, а через последовательно соединенные второй узел 8 задержки и второй элемент ИЛИ 16 к входу записи третьего буферного регистра 6. Шестой управляющий выход Q6 блока ввода-вывода 1 подключен к вторым входам второго 16 и третьего 17 элементов ИЛИ и через первый узел 7 задержки к второму входу первого элемента ИЛИ 15. Седьмой управляющий выход Q7 блока ввода-вывода 1 подключен к вторым входам первого 7 и второго 8 узлов задержки.

Последовательный информационный вход-выход 18, тактовый вход 19, пусковой вход 20, параллельные информационные входы-выходы 21 и управляющие входы-выходы 22 блока ввода-вывода 1 являются соответствующими входами-выходами устройства.

Буферные регистры 4, 5 и 6 могут быть выполнены на ИМС К588ИР1, блоки ключей 12, 13 и 14 - на ИМС 564КТ3, блок сумматоров 11 по модулю два - на ИМС 564ЛП2 [9].

Коммутатор 10 может быть выполнен на 16-ти парах ключей, реализованных на ИМС 564КТ3. Управляющие входы четных ключей объединены и подключены к управляющему входу коммутатора непосредственно, а нечетных - через инвертор. Таким образом, информационные входы четных ключей являются первыми (A) входами, а нечетных ключей - вторыми (B) входами коммутатора 10.

Блок памяти 3 содержит ПЗУ, реализованное на ИМС 573РФ4, и ОЗУ на ИМС 537РУ9.

Центральным узлом устройства является микропроцессорный блок 23, входящий в состав блока ввода-вывода 1. В процессе работы устройства в любом из режимов микропроцессор опрашивает признаки подключенных к общей шине 2 узлов, выставляя последовательно адрес каждого, с целью выявления узла, готового к обмену информацией, и при положительном результате осуществляет этот обмен. В приведенных ниже примерах реализации узлов устройства наименование управляющих сигналов, поступающих на эти узлы, дано применительно к процессору К1801ВМ2 [7].

Предлагаемое устройство работает в следующих режимах: ввода-вывода информации и кодирования-декодирования информации.

Режим ввода-вывода информации.

На фиг. 2 представлена функциональная схема блока ввода-вывода 1. Блок ввода-вывода 1 содержит микропроцессорный блок 23, параллельный порт ввода-вывода 24, дешифратор 25 и последовательный порт ввода-вывода 26. Входы-выходы микропроцессорного блока 23, параллельного порта ввода-вывода 24, последовательного порта ввода-вывода 25 и входы дешифратора 25 подключены к общей шине 2.

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

Параллельный порт ввода-вывода 24 предназначен для обмена параллельной информацией и управляющими сигналами между оконечным оборудованием данных (ООД) и предлагаемым устройством, осуществляемого соответственно по параллельным информационным входам-выходам 21 и управляющим входам-выходам 22.

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

На фиг. 3 в качестве примера реализации представлена функциональная схема дешифратора 25, который содержит последовательно соединенные буферный регистр 27, двоично-десятичный дешифратор 28 и блок 29 элементов И 30, число которых равно числу дешифрируемых сигналов.

Дешифратор работает следующим образом. По шине 2 на информационные входы буферного регистра 27 поступает код адреса опрашиваемого узла, а на управляющий вход записи с некоторой задержкой - сигнал "Обмен" (SYNC применительно к процессору К1801ВМ2), который фиксирует этот адрес в буферном регистре 27. После фиксации адреса с управляющего выхода буферного регистра 27 выдается сигнал "Подтверждение", поступающий через шину адрес - данные 2 в микропроцессорный блок 23. С выхода буферного регистра 27 комбинация адреса поступает на вход двоично-десятичного дешифратора 28, который преобразует код адреса в позиционный сигнал, поступающий в блок 29 элементов И 30.

Микропроцессор в процессе взаимодействия с узлами устройства осуществляет две операции: чтение и запись информации. Поэтому каждый позиционный сигнал с выхода двоично-десятичного дешифратора 28 поступает на первые входы двух элементов И, на вторые входы которых поступают управляющие сигналы "Чтение" (DIN) или "Запись" (DOIT) от микропроцессорного блока 23, при этом на выходах элементов И формируются сигналы чтения или записи информации для соответствующих узлов устройства, поступающие на выходы дешифратора 24:
семь управляющих сигналов Q1 - Q7, поступающих на выходы блока ввода-вывода 1, четыре управляющих сигнала: "Чтение 1" ("ЧТ 1"), "Чтение 2" ("ЧТ 2"), "Запись 1" ("ЗП 1"), "Сброс" - в параллельный порт ввода-вывода 24 и пять управляющих сигналов: "Чтение 3" ("ЧТ 3"), "Чтение 4" ("ЧТ 4"), "Чтение 5" ("ЧТ 5"), "Запись 2" ("ЗП 2") и "Запись 3" ("ЗП 3") - в последовательный порт ввода-вывода 26.

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

Буферный регистр 27 может быть реализован на микросхеме К588ИР1, двоично-десятичный дешифратор 28 - К564ИД1, элементы И - 564ЛА7 [8].

Рассмотрим работу устройства в режиме ввода-вывода информации через параллельный порт ввода-вывода 24, пример реализации которого приведен на фиг. 4.

Порт ввода-вывода 24 содержит буферный регистр ввода 31 информации, буферный регистр вывода 32 информации, триггер признаков ввода 33, триггер признаков вывода 34, два ключа 35 и 36.

Информация от ООД поступает в параллельном коде на входы 21 блока ввода-вывода 1 и далее на информационные входы буферного регистра ввода 31, и по сигналу "Ввод" от ООД, поступающему на вход 22 блока ввода-вывода 1 (фиг. 1) и далее на записывающий вход буферного регистра 31, записывается в последнем. Одновременно сигал "Ввод" поступает на вход триггера признаков ввода 33, устанавливая его в состояние "1", которое поступает на информационный вход первого ключа 35. Сигнал с инверсного выхода триггера 33 поступает на выход порта и далее на управляющий вход-выход 22 блока ввода-вывода 1 в ООД, сигнализируя о запрете ввода следующего слова информации (сигнал "Запрет").

Микропроцессор, находясь в цикле опроса узлов устройства, периодически опрашивает и анализирует состояние ключа 35, подавая сигнал "Чтение 1" через дешифратор 25, поступающий на управляющий вход ключа 35.

При наличии информации в буферном регистре ввода 31 на выходе ключа 35 появится сигнал, который поступает на выход порта и далее на шину 2 как признак "Наличие информации от ООД". Микропроцессор, обнаружив этот признак, считывает информацию с буферного регистра 31, для чего он через дешифратор 25 выставляет сигнал "Чтение 2", поступающий на считывающий вход буферного регистра 31, при этом информация в параллельном коде поступает на выход порта и далее в шину 2.

После записи информации в ОЗУ микропроцессор через дешифратор сигналом "Сброс" сбрасывает триггер 33, в результате чего с выхода триггера снимается сигнал "Запрет", разрешая ввод с ООД следующего слова информации.

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

Этим же сигналом триггер признаков вывода 34 устанавливается в состояние "1", которое через управляющий вход-выход 22 блока ввода-вывода поступает в ООД как сигнал "Наличие информации". Сигнал с инверсного выхода триггера 34 поступает на информационный вход второго ключа 36. Микропроцессор, опрашивая ключ 36 сигналом "Чтение 1", поступающим на управляющий вход ключа 36 через дешифратор 25, обнаруживает признак занятости буферного регистра 32 и поэтому не выводит из ОЗУ очередное слово информации. ООД, обнаружив сигнал "Наличие информации", выдает сигнал "Вывод", поступающий по управляющему входу-выходу 22 блока ввода-вывода 1 на считывающий вход буферного регистра 32, считывая с него информацию, которая через входы-выходы 21 блока ввода-вывода 1 поступает в ООД. Одновременно сигналом "Вывод" сбрасывается триггер 34 признака вывода, в результате чего сбрасывается признак "Наличие информации" и в очередном цикле разрешается вывод слова из ОЗУ в порт 24.

Буферные регистры 31 и 32 могут быть реализованы каждый из двух ИМС К588ИР1, триггеры 33 и 34 - на ИМС 564ТМ2, ключи 35 и 36 - на ИМС 564КТ3 [9] .

На фиг. 5 в качестве примера реализации приведена функциональная схема последовательного порта ввода-вывода информации 26, который содержит последовательно-параллельные регистры по вводу 37 и выводу 38 информации, параллельные буферные регистры по вводу 39 и по выводу 40 информации, двоично-десятичный счетчик 41, элемент И 42, триггеры 43 и 44, ключи 45 и 46, элементы ИЛИ 47 и 48.

Ввод информации осуществляется следующим образом. Информация в последовательном коде с входа-выхода 18, тактовая частота F_т с входа 19 и сигнал "Пуск" с входа 20 блока ввода-вывода 1 устройства поступают соответственно на информационный и записывающий входы последовательно-параллельного регистра ввода 37 и установочный вход счетчика 41 (через элемент ИЛИ 48). Кроме того, тактовая частота F_т поступает также на счетный вход счетчика 41. Информация записывается в регистре 37, а счетчик 41 устанавливается в нулевое состояние и через число тактов, равное разрядности слова, например 16, через элемент И 42, играющий роль дешифратора 16 такта, выдает сигнал на записывающий вход параллельного буферного регистра 39, фиксируя информацию, поступающую на его входы с выхода последовательно-параллельного регистра ввода 37. Одновременно с этим сигнал с выхода элемента И 42 через элемент ИЛИ 47 устанавливает триггер 44 в состояние "1", которое поступает на информационный вход ключа 45, сигнализируя микропроцессору о наличии информации из канала связи. Микропроцессор, находясь в цикле опроса, обнаруживает этот сигнал, подавая для этого на управляющий вход ключа 45 по шине 2 через дешифратор 25 сигнал "Чтение 3", после чего формирует сигнал "Чтение 4", поступающий по шине 2 через дешифратор 25 на считывающий вход буферного регистра 39, считывая с него информацию, которая поступает на выход порта и далее в шину 2. После этого микропроцессор выдает сигнал "Запись 2", поступающий по шине 2 через дешифратор 25 на сброс триггера 44, устанавливая его в состояние "0", в результате чего становится возможным прием следующего слова информации.

В режиме вывода информации последняя по шине 2 поступает на информационные входы буферного регистра 40 и сигналом "Запись 2", поступающим от микропроцессора по шине 2 через дешифратор 25, записывается в этом регистре. Одновременно этим же сигналом триггер 44 устанавливается в нулевое состояние, которое будет присутствовать на информационном входе ключа 45 и при опросе его микропроцессором будет свидетельствовать о запрете ввода в буферный регистр 40 очередного слова информации.

После записи первого слова информации в буферный регистр 40 микропроцессор по шине 2 через дешифратор 25 выдает сигнал "Чтение 5", поступающий через элемент ИЛИ 48 на установочный вход двоично-десятичного счетчика 41, устанавливая его в нулевое состояние, на первый вход триггера 43, устанавливая его в единичное состояние, через элемент ИЛИ 47 - на записывающий вход параллельно-последовательного регистра по выводу 38 информации, осуществляя запись в него информации с выходов буферного регистра вывода 40, и на первый вход триггера 44, устанавливая его в единичное состояние и снимая тем самым запрет на ввод очередного слова информации.

Сигналом с выхода триггера 43 открывается ключ 46 и информация под действием тактовой частоты F_т, поступающей на тактовый вход регистра 38, выдается на вход-выход 18 блока ввода-вывода 1.

Вывод последующих слов информации в буферный регистр 40 осуществляется по сигналам, периодически выдаваемым через 16 тактов счетчиком 41 через элемент И 42. Через 16 тактов после записи последнего слова в буферный регистр 40 микропроцессор по шине 2 через дешифратор 25 выдает сигнал "Запись 5", сбрасывающий триггер 43 в нулевое состояние и отключающий тем самым выход регистра 38 от канала связи. Одновременно в цикле опроса прекращается анализ ключа 45 на возможность ввода информации.

Последовательно-параллельные регистры 37 и 38 могут быть реализованы на четырех ИМС 564ИР9, буферные регистры 39 и 40 каждый - на двух ИМС 588ИР1, счетчик 41 - ИМС 564ИЕ10, элемент И 42 - на ИМС 564ЛА7, триггреры 43 и 44 - на ИМС 564ТМ2, ключи 45 и 46 - на ИМС 564КТ3, элементы ИЛИ - на ИМС 564ЛЕ5 [9].

На фиг. 6 представлен пример реализации функциональной схемы микропроцессорного блока 23 на базе процессора К1801ВМ2. Микропроцессорный блок содержит собственно процессор 49, регистр сдвига 50 и элемент ИЛИ 51. Регистр сдвига и элемент ИЛИ образуют схему формирования сигнала "Ответ". Процессор содержит входы-выходы AD0-AD15, по которым процессор выдает адреса опрашиваемых узлов и получает или выдает информацию, вход "Подтверждение" (AR), по которому процессор получает сигнал, подтверждающий прием адреса дешифратором, выходы "Обмен" (SYNC), "Чтение" (DIN), "Запись" (DOIT), по которым процессор формирует сигналы, поступающие в дешифратор при организации взаимодействия его с узлами устройства, а также выход "Байт" (WIBT), по которому процессор выдает сигнал в ОЗУ. Этот сигнал совместно с младшим разрядом адреса (нулевым) определяет, в какой из байтов ОЗУ происходит запись. Например, значение "0" сигнала означает запись в ОЗУ одного из двух байтов, в разряд "0" адреса указывает, какой байт конкретно будет записываться (младший, старший). Указанные выше выходы процессора образуют общую шину 2.

Регистр сдвига 50 предназначен для задержки сигналов "Чтение" или "Запись" и формирования сигнала "Ответ" для процессора по входу RPLY. Сигнал "Ответ" говорит о том, что в режиме чтения информации процессором из опрашиваемого узла эта информация выставлена по шине 2, а в режиме записи - информация записана в узел. Величина задержки, обеспечиваемой регистром сдвига 50, выбирается исходя из надежного срабатывания взаимодействующих с процессором узлов.

Регистр сдвига 50 может быть реализован на ИМС 564ИР2, элемент ИЛИ - на ИМС 564ЛЕ5.

Режим кодирования-декодирования информации.

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

Известно [6, с.119], что кодовый многочлен C(x) можно представить в виде
С(x) = x^N-K·I(x) + t(x), (5)
где
I(x) - информационный многочлен;
t(x) - остаток от деления многочлена x^N-K·I(x) на образующий многочлен G(x).

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

На фиг. 7 схематически представлено распределение области ОЗУ, используемой при кодировании. Эта область содержит шесть зон. В 1 и 2 зонах объемом каждая 241 байт записываются информационные массивы 1 и 2 полосы соответственно. 5 и 6 зоны дублируют 1 и 2 зоны. В 3 и 4 зонах будут записаны проверочные символы кода РС. Объем 3 и 4 зон каждой составляет 16 восьмиразрядных слов.

Первоначальная запись информации из блока ввода-вывода осуществляется одновременно по первой полосе в 1 и 5 зоны, по второй полосе во 2 и 6 зоны.

Отведение K ячеек памяти под запись информационных символов и N - K ячеек памяти с первоначальным "нулевым" значением и последующей записью в них проверочных символов кода РС означает автоматическое умножение информационного многочлена I(x) на x^N-K в соответствии с выражением (5).

В дальнейшем в процессе кодирования кодом РС содержимое 1 и 2 зон постоянно обновляется для хранения промежуточных результатов деления многочлена x^N-K· I(x) на образующий многочлен G(x) (коэффициенты образующего многочлена хранятся в ПЗУ), а содержимое 5 и 6 зон остается неизменным. В результате деления в 3 и 4 зонах окажутся записанными проверочные символы кода РС (остаток от деления).

Кодирование информации осуществляется по программе, хранящейся в ПЗУ блока памяти 3, в соответствии с алгоритмом, представленным на фиг.8. Операторы алгоритма имеют следующее назначение.

Первым оператором осуществляется запись в регистр общего назначения (РОН) 1 микропроцессора числа K информационных символов кода РС (K = 225).

Второй оператор считывает из зон 1 и 2 ОЗУ блока памяти 3 старшие коэффициенты (байты) многочлена x^N-K · I(x) и пересылает их в первый буферный регистр 4, выставляя по шине 2 адрес этого регистра. Дешифратор 25 дешифрирует этот адрес и управляющим сигналом Q4, поступающим на записывающий вход этого регистра, фиксирует в нем этот коэффициент (фиг.1).

Третий оператор осуществляет проверку на конец кодирования внешним кодом, для чего содержимое РОН 1 уменьшается на единицу и сравнивается с нулем. При отличии результата от нуля осуществляется переход к четвертому оператору, в противном случае - переход к программе кодирования информации внутренним кодом.

Четвертый оператор осуществляет запись в РОН 2 микропроцессора числа, равного (N-K - 1), в нашем примере (N-K-1)= 15.

Пятым оператором осуществляется запись из ПЗУ очередного (на первом этапе деления многочленов x^N-K · I(x) и G(x) - старшего) коэффициента многочлена G(x) через коммутатор 10 во второй буферный регистр 5, выставляя для этого по шине 2 адрес этого регистра. Дешифратор 25 дешифрирует этот адрес и управляющим сигналом Q5 через первый элемент ИЛИ 15 фиксирует этот коэффициент во втором буферном регистре 5. При этом на выходе умножителя 9 получается результат умножения содержимого обоих регистров.

Шестым оператором осуществляется пересылка результата умножения в РОН 3 микропроцессора, для чего микропроцессор через дешифратор 25 формирует управляющий сигнал Q1, в результате чего открывается первый блок ключей и результат произведения поступает по шине 2 в РОН 3.

Седьмым оператором в арифметико-логическом устройстве (АЛУ) микропроцессора содержимое РОН 3 складывается с текущими коэффициентами многочлена, хранящегося в зонах 1 и 2, следующими по порядку за сокращаемым коэффициентом. На первом этапе, когда сокращается старший коэффициент многочлена x^N-K·I(x), такими текущими коэффициентами являются коэффициенты, следующие за старшим. При этом результат сложения записывается по адресу текущего коэффициента, и совокупность этих коэффициентов образует промежуточный (модифицированный) многочлен, с коэффициентами которого на последующих этапах деления будут осуществляться операции умножения и сложения.

Восьмой оператор осуществляет проверку на конец процедуры умножения содержимого первого и буферного регистров на коэффициенты образующего многочлена G(x), для чего содержимое РОН 2 уменьшается на единицу и сравнивается с нулем. При отличии результата вычитания от нуля осуществляется переход к пятому оператору, в противном случае - переход к второму оператору, начиная процедуру сокращения очередного старшего коэффициента модифицированного многочлена.

В предлагаемом устройстве кодирование и декодирование информации осуществляются сразу по двум полосам. Поэтому буферные регистры 4, 5 и 6 содержат по два восьмиразрядных регистра, а умножитель 9 содержит два восьмиразрадных умножителя.

Применительно к процессору К1902ВМ2 к набору элементов, указанных в примерах реализации, для выполнения операторов 1, 3, 4 и 8 требуется ≃ 6 мкс для каждого, операторов 2, 5 и 7 - ≃ 15 мкс. Кодирование одного блока (225·16) дв. символов кодом РС потребует число команд, равное N_к = (4·15+4) 225+1 = 401 команда, и по времени займет T_внешн. ≃ 0,16 с. На кодирование одного бита информации в среднем потребуется 2,5 команды.

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

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

Чисто программная реализация операции умножения двух чисел в поле GF (2^m) потребует 18 команд [10].

Выигрыш предлагаемого устройства по числу команд для операции умножения примерно составляет 4,5 раза. Примерно такой же будет и выигрыш устройства во всей операции кодирования кодом РС, так как операция умножения является наиболее частой.

После завершения кодирования информации внешним кодом микропроцессор осуществляет кодирование каждого 16-разрядного слова внутренним (24, 16) кодом, добавляя к 16 информационным символам 8 проверочных. Кодирование осуществляется табличным способом.

Однако прямое табличное кодирование, использованное в прототипе, когда 16 информационных символов являются адресом ячейки, в которой хранятся 8 проверочных символов, требует большого объема памяти. Поэтому в предлагаемом устройстве используется табличное кодирование по частям с длиной каждой части l = 8 [11], что позволяет сократить объем памяти с 2¹⁶ до 2⁸ ячеек.

На фиг. 9 представлена блок-схема алгоритма кодирования информации внутренним кодом (пример). Операторы алгоритма имеют следующее назначение.

Оператор 1 устанавливает исходные данные, к которым относятся
начальный адрес массива M 1 символов кода РС (информационных комбинаций внутреннего кода),
начальный адрес массива M 2 остатков,
начальный адрес массива M 3 проверочных символов внутреннего кода,
начальное значение счетчика шага символов в кодовом блоке кода РС, например N = 241.

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

Оператор 2 формирует адрес ячейки массива M 2, где хранится остаток от деления первого байта текущего блока внутреннего кода (в начале алгоритма первого) на образующий многочлен g(x).

Оператор 3 по сформированному в операторе 2 адресу извлекает остаток и пересылает его в РОН микропроцессора.

Оператор 4 извлекает из массива M 1 второй байт текущего блока.

Оператор 5 складывает второй байт текущего слова с содержимым РОНа.

Оператор 6 выделяет младший байт в результате сложения (операция обнуления старшего байта, характерная для системы команд машин типа "Электроника-60").

Оператор 7 по адресу, равному содержимому младшего байта этого результата, считывает из массива M 2 остатков проверочный символ и записывает его в массив проверочных символов M 3.

Оператор 8 уменьшает значение счетчика числа символов на единицу.

Оператор 9 проверяет условие равенства 0 показаний счетчика. При невыполнении условия равенства 0 осуществляется переход к оператору 2, при выполнении - окончание алгоритма.

Загрузка микропроцессора программой кодирования внутренним кодом по описанному выше алгоритму составил около 1690 команд, или 0,29 команды на бит информации.

Результирующая загрузка микропроцессора на кодирование внутренним и внешним кодами составит примерно T_рез=T_внеш. + T_внутр=1,37+0,29 = 1,66 к/бит.

Режим декодирования информации.

В режиме ввода информации из канала связи, как говорилось ранее при описании работы блока ввода-вывода 1, информация записывается в ОЗУ блока памяти 3. Микропроцессор и ОЗУ, используемые в устройстве, являются 16-разрядными. На фиг. 10 схематично представлено распределение ячеек ОЗУ для записи информации, принимаемой из канала связи.

На фиг. 11 представлена блок-схема алгоритма декодирования закодированной внутренним кодом информации. Алгоритм использует табличный метод декодирования по частям [11]. Назначение операторов алгоритма следующее.

Оператором 1 устанавливаются исходные данные, к которым относятся
число блоков внутреннего кода в блоке кода РС, например, равное 241,
начальный адрес зоны ОЗУ, в которой хранится информация, принятая из канала связи,
начальный адрес зоны ОЗУ, в которой хранятся признаки блоков внутреннего кода, например "0" - кодовый блок без ошибки или с необнаруженной ошибкой, "1" - кодовый блок с обнаруженной ошибкой.

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

По текущему (начальному при начале кодирования) адресу ячейки информационной зоны ОЗУ сосчитывается байт со старшими коэффициентами и записывается в РОН микропроцессора, так как при этом происходит размножение байта, то необходима операция "обнуления" (занесения константы) старшего байта этого РОНа. Эта операция занесения константы повторяется при каждом чтении информации из ОЗУ. При этом старший байт РОНа используется для указания определенной зоны в ОЗУ, а младший - для указания адреса байта в этой зоне.

По адресу содержимого в младшем байте РОНа с учетом константы в старшем байте РОНа происходят обращение к зоне остатков и считывание из нее промежуточного остатка от деления старших коэффициентов декодируемого блока на образующий многочлен g(x) и запись в этот же РОН. Затем содержимое РОНа складывается по модулю два со следующим байтом декодируемого блока и записывается в этом же РОНе.

Оператор 3 определяет синдром декодируемого блока, для чего по адресу содержимого РОНа происходят обращение к соответствующей ячейке зоны остатков и считывание результата от деления содержимого РОНа на образующий многочлен g(x), который записывается в этом же РОНе. После этого содержимое РОНа складывается по модулю два с проверочным байтом декодируемого блока, результат сложения, являющийся синдромом, записывается в этом же РОНе.

Оператор 4 осуществляет анализ синдрома. Если синдром равен нулю, то оператор 5 осуществляет запись признака "0" в соответствующую декодируемому блоку ячейку зоны признаков, если синдром отличен от нуля, то оператор 6 осуществляет в эту ячейку запись признака "1".

Операторы 7 и 8 осуществляют проверку на окончание процедуры декодирования. Для этого оператор 7 уменьшает на единицу содержимое ячейки памяти (РОНа), где хранится текущий номер декодируемого блока, а оператор 8 сравнивает значение этого номера с нулем. Если N = 0, то происходит окончание процедуры декодирования, если N≠0, то осуществляется переход к оператору 2 и процедура декодирования продолжается.

В результате декодирования в одной части ОЗУ будет записан информационный массив с числом 16-разрядных кодовых блоков, равный N, а в другой части ОЗУ будет записан массив признаков (стираний) такого же объема.

Алгоритм несколько усложняется при использовании кода в режиме исправления однократных ошибок. Детальная проработка этого алгоритма показала, что затраты машинного времени составляют 0,86 команды на бит для самого тяжелого варианта декодирования (в 241 символах 16 стираний и 225 исправлений одиночных ошибок).

Алгоритм декодирования внешнего кода РС, являющегося частным случаем кода БЧХ, по существу изложен в [7, с. 167 - 175]. Исходными данными для декодирования внешнего кода являются полученные при декодировании внутреннего кода декодированные кодовые комбинации, номера (локаторы) стертых кодовых комбинаций внутреннего кода.

Обобщенный алгоритм декодирования внешнего кода БЧХ (РС) представлен на фиг. 12.

В первой операции алгоритма осуществляется вычисление синдромного многочлена S(x). Синдромный многочлен имеет вид
S(x) = S₀x^R-1 + S₁x^R-2 + ... + S_R-1; R = n - K. (6)
Коэффициенты многочлена определяются как значения кодового многочлена C(x) длиной N при подстановке в него значений [6, с. 188] , где D - кодовое расстояние кода; m₀ - целое положительное число, не превышающее -2.

Например, для m₀ = 0 и кода РС с образующим многочленом (3) (D = 17) в кодовый многочлен необходимо подставить значения α^o,α;α²,α³...α¹⁵ .

Вычисление коэффициентов синдромного многочлена удобно производить в виде рекуррентного соотношения по формуле (4).

При отсутствии искажений коэффициенты S_m равны нулю, при наличии искажений они отличны от нуля и вместе с локаторами (номерами) стертых символов, определенными при декодировании внутреннего кода, используются далее для декодирования кода РС.

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

На фиг. 14 представлены временные диаграммы управляющих сигналов, формируемых микропроцессором при вычислении коэффициентов S_m.

Операторы алгоритма имеют следующее назначение.

Оператор 1 устанавливает исходные данные, к которым относятся
начальное значение адреса B₀ + 1 массива элементов поля в ПЗУ, где B₀ - константа,
начальное значение счетчика коэффициентов синдромного многочлена R__→ (в ячейку по адресу A заносится значение R, в качестве примера R = 16),
начальное значение адреса A₀ + 1 массива коэффициентов S_m синдромного многочлена, где A₀ - константа.

Оператор 2 устанавливает начальное значение C + 1 массива информации в ОЗУ, где C - константа. Начальное значение адресов массивов записывается в РОНах, при этом используется автоинкрементный способ адресации.

Оператор 3 по сигналу Q4 (фиг. 14 ж) осуществляет запись из ПЗУ блока памяти 3 по шине 2 в первый буферный регистр 4 (фиг. 1) очередного элемента поля (в начале алгоритма α^o из ячейки с адресом B₀ + 1).

Оператор 4 по сигналу Q5 (фиг. 14 б) осуществляет запись из ОЗУ блока памяти 3 по шине 2 через коммутатор 10 во второй буферный регистр 5 очередного символа C_j ( в начале алгоритма C₁ из ячейки с адресом C + 1). При этом на выходе умножителя 9 получается результат умножения C_iα^m, который поступает на первые входы блока сумматоров 11 по модулю два.

Операторы по сигналу Q6 (фиг. 14 г) осуществляют запись из ОЗУ блока памяти 3 по шине 2 через коммутатор 10 в третий буферный регистр 6 символов C₂ - C_N, при этом с вводом каждого символа на выходе блока сумматора по модулю два 11 образуется сумма предыдущего результата с вводимым символом, которая через коммутатора 10 (при снятии сигнала Q6 коммутатор устанавливается в противоположное состояние) поступает на информационные входы второго буферного регистра 5, где фиксируется сигналом Q6, задержанным в первом узла 7 задержки (фиг. 14 д), величина задержки определяется управляющим сигналом Q7 (тактируемая задержка).

На умножителе 9 эта сумма умножается на величину α^m и результат умножения поступает на блок 11 сумматоров по модулю два, а с его выхода через коммутатор 10 во второй буферный регистр, где он фиксируется очередным сигналом Q6.

Оператор N + 4 после ввода последнего символа C_N выдает сигнал Q2 на второй блок ключей, и значение коэффициента S_m записывается в ОЗУ по соответствующему адресу в массив коэффициентов синдромного многочлена.

Операторы N + 5 и N + 6 перед вычислением следующего коэффициента синдромного многочлена осуществляют проверку на окончание алгоритма, т.е. не является ли очередной коэффициент S_m последним. Для этого оператор N + 5 уменьшает содержимое ячейки A на единицу и записывает результат в ту же ячейку, а оператор N + 6 сравнивает результат с нулем. Положительный результат сравнения означает, что все R коэффициентов многочлена вычислены и записаны в соответствующий массив ОЗУ. При отрицательном результате сравнения осуществляются переход к оператору 2 и повторение алгоритма с очередным α^m.
Загрузка микропроцессора программой вычисления коэффициентов синдромного многочлена по описанному выше алгоритму составляет около 4000 команд.

В результате осуществления описанного алгоритма будет сформирован массив М₀ коэффициентов синдромного многочлена, записанных по адресам (A₀ + 1) - (A₀ + R).

Во второй операции обобщенного алгоритма декодирования внешнего кода (фиг. 12) осуществляется вычисление многочлена локаторов стираний λ(x) .

Многочлен локаторов стираний имеет вид

где
Y_j - локаторы (номера) стираний, полученные при декодировании внутреннего кода;
λ_i - значения коэффициентов;
s - число стираний (см. [7], с. 169 формула Б 6, в которой
σ_de=λ_i,aZ^s-e=X^s-i) ).

Приравнивая коэффициенты при неизвестных с одинаковыми степенями в левой и правой частях уравнения (7), можно найти значения коэффициентов λ_i .

При программной реализации удобнее определение значений коэффициентов проводить в виде
λ_i^(j)=λ_i^(j-1)+Y_jλ_i-1^(j-1) (8)
(см. аналогично [7], с. 173, формула Б 22),
где
λ_i^(j-1) - i-й коэффициент после обработки (j - 1)-го локатора стираний, .

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

На первом этапе (j = 1) определяется коэффициент
λ₁=λ¹₁=Y₁.(9)
На втором этапе определяются коэффициенты

На третьем этапе определяются коэффициенты

На s-м этапе определяются коэффициенты

В качестве примера на фиг. 15 приведена блок-схема алгоритма определения коэффициентов многочлена локаторов стираний λ(x) , на фиг. 16 - состояние РОНов, первого и второго буферных регистров в зависимости от номера этапа и номера оператора.

Операторы алгоритма имеют следующее значение.

Оператор 1 устанавливает исходные данные, к которым относятся
начальный адрес A₁ + 1 массива М 1 локаторов стираний, записываемый в РОН 0, где A₁ - константа,
начальный адрес A₂ + 1 массива M 2 коэффициентов многочлена локаторов стираний, записываемый в РОН 2 и РОН 4, где A₂ - константа,
начальное значение номера этапа j = 1, записываемое в счетчике числа этапов,
адрес ячейки L, в которой записан последний локатор стираний, например A₁ + 3, если число стираний s = 3.

Оператор 2 осуществляет запись из массива M 1 в массив M 2 первого локатора стираний Y₁, формируя тем самым коэффициент λ₁ в соответствии с выражением (9). Для этого содержимое ячейки, адрес которой указан в РОН 0, записывается в ячейку, адрес которой указан в РОН 4. При этом после каждого обращения к массивам M 1 и M 2 адреса, хранящиеся в РОН 0 и РОН 4, увеличивается на единицу.

Оператор 3 проверяет условие, является ли следующий локатор Y_j последним, для чего он сравнивает адрес этого локатора, хранящийся в РОН 0, с адресом ячейки L, в которой записан последний локатор стираний. При положительном результате сравнения алгоритм заканчивается, при отрицательном осуществляется переход к оператору 4.

Оператор 4 осуществляет запись номера завершенного этапа j, записанного в счетчике этапов, в РОН 5.

Оператор 5 осуществляет переход к следующему этапу, увеличивая содержимое счетчика числа этапов на единицу: j = j + 1.

Оператор 6 осуществляет считывание из массива M 1 в РОН 1 и в первый буферный регистр 4 (фиг. 1) текущего локатора стираний Y_j (после первого этапа Y_j = Y₂, после второго Y_j = Y₃ и так далее).

Оператор 7 осуществляет считывание из массива M 2 в РОН 3 содержимого ячейки, адрес которой записан в РОН 2, с последующим увеличением адреса на единицу (после первого этапа по этому адресу сосчитывается коэффициент λ₁= λ⁽₁¹⁾ ).

Оператор 8 определяет коэффициент λ⁽₁^j) путем суммирования содержимого РОН 3 и РОН 1 с последующей записью результата в РОН 1 (после первого этапа в соответствии с выражением (10), после второго - с выражением (12) и так далее).

Оператор 9 осуществляет считывание предыдущего результата из РОН 1 в массив M 2 по адресу, который записан в РОН 4, с последующим увеличением этого адреса на единицу.

Оператор 10 осуществляет считывание содержимого РОН 3 во второй буферный регистр 5 (фиг. 1), при этом происходит вычисление очередного коэффициента многочлена λ(x) .

Оператор 11 осуществляет запись результата умножения в РОН 1.

Операторы 12 и 13 осуществляют проверку на окончание этапа, вычитая единицу из содержимого РОН 5 и сравнивая результат вычитания с нулем. При положительном результате сравнения осуществляется переход к оператору 14. При отрицательном результате сравнения осуществляется переход к оператору 7 и определение следующего коэффициента этапа.

Оператор 14 осуществляет считывание содержимого РОН 1 и запись его в массив M 2 по адресу, который записан в РОН 4, с последующим увеличением этого адреса на единицу, и переход к оператору 3.

В результате осуществления описанного алгоритма будет сформирован массив M 2 коэффициентов многочлена локаторов стирания и промежуточных коэффициентов полученных в соответствии с выражениями (9 - 15) и записанных по адресам (A₂ + 1) - (A₂ + 136) (при числе стираний меньшем, 16 часть массива остается свободной).

На фиг. 17 представлена структура массива M 2 для этого случая.

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

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

где
e_j - значение ошибки;
d_k - значение стертого символа;
x_j - локатор ошибки;
Y_k - локатор стирания (см. [7], с. 169, формула Б 5),
а также с учетом того, что

получим
T(x) = T₀x^R-1-S + T₁x^R-2-S + ... + T_R-2-Sx + T_R-1-S, (18)
где

где
величины определены первой и второй операциями обобщенного алгоритма.

В качестве примера на фиг. 18 приведена блок-схема алгоритма определения коэффициента модифицированного синдромного многочлена T(x).

Операторы алгоритма имеют следующее назначение.

Оператор 1 устанавливает исходные данные, к которым относятся
условный начальный адрес (A₀ + 0) массива M 0 коэффициентов синдромного многочлена, предшествующий адресу A₀ + 1 ячейки, в которой хранится коэффициент S₀, адрес записывается в РОН 0,
начальный адрес массива M 3 (A₃ + 1) коэффициентов модифицированного синдромного многочлена, записываемый в РОН 2,
начальное значение счетчика числа коэффициентов модифицированного синдромного многочлена N_мод = K = 2t, где t - скорость направляемых кодом РС ошибок, , где ]·[ означает целую часть.

В качестве примера рассмотрим случай, когда число стираний S = 3 и, следовательно, K = 12.

Система уравнений для нахождения коэффициентов T₀, T₁ ... , T₁₁ имеет вид

Оператор 2 записывает в счетчик числа стираний число стираний, в нашем примере N_ст = 3.

Оператор 3 записывает в РОН 4 адрес A₂ + 1 ячейки массива M 2, в которой хранится первый коэффициент λ₁ многочлена локаторов стираний.

Оператор 4 присваивает переменной L₁ значение, равное 0.

Оператор 5 увеличивает содержимое РОН 0 на величину S + 1.

Оператор 6 считывает из массива M 0 содержимое ячейки с адресом <РОН О>, то есть в нашем примере с адресом <A+4> , по которому хранится коэффициент S_S= S₃, и записывает его в третий буферный регистр (фиг. 1) по сигналу Q6.

Оператор 7 считывает из массива M 0 содержимое ячейки с адресом <РОН О-1>, , по которому хранится коэффициент S_N-1 (в нашем примере λ₁ ), и записывает в первый буферный регистр 4 по сигналу Q4.

Оператор 8 увеличивает содержимое РОН 4 на величину L₁.

Оператор 9 считывает из массива M 2 содержимое ячейки с адресом РОН 4, по которому хранится коэффициент (в нашем примере λ₁ ), и записывает его во второй буферный регистр 5 по сигналу Q5. При этом адрес, записанный в РОН 4, увеличивается на единицу. На выходе умножителя 9 сформируется результат S₂·λ₁ , который поступит на первые входы сумматора 11 по модулю два, на вторые входы которого поступает сигнал с выхода третьего буферного регистра 6, в котором был записан коэффициент S₃.

Сигналом Q5, задержанным во втором элементе задержки 8, выходной сигнал сумматора 11, равный (S₂λ₁+ S₃) , поступающий через коммутатор 10 на входы третьего буферного регистра 6, записывается в этом регистре.

Оператор 10 увеличивает значение переменной L₁ на единицу.

Оператор 11 уменьшает значение, записанное в счетчике стираний, на единицу.

Оператор 12 проверяет условие равенства нулю значения счетчика числа стираний. При отрицательном результате сравнения происходит переход к оператору 7, при положительном - к оператору 13. В нашем примере N - 1 = 2, поэтому операторы 7 - 12 повторяются два раза.

При первом повторении оператор 7 сосчитывает коэффициент S₁, а при втором - S₀.

Оператор 8 при первом повторении сосчитает содержимое ячейки по адресу РОН 4 = A₂ + 3, то есть коэффициент λ₂ , а при втором - по адресу РОН 4 = A₂ + 6, то есть коэффициент λ₁ .

В результате первого повторения в третьем буферном регистре 6 образуется сумма S₁λ₂+ S₂λ₁+ S₃ , а в результате второго - коэффициент T₀, при этом условие N = 0 будет выполнено и осуществится переход к оператору 13.

Оператор 13 по сигналу Q3 через третий блок ключей 14 записывает первый коэффициент T₀ в массив M 3, коэффициенты модифицированного синдрома по адресу содержимого РОН 2 = A₃ + 1, то есть в первую ячейку массива M 3, при этом адрес в РОН 2 увеличится на единицу и станет равным РОН 2 = A₃ + 2.

Оператор 14 уменьшает на единицу значение K (в нашем примере K станет равным 11).

Оператор 15 проверяет равенство нулю значения K. Если K = 0, то алгоритм закончен и в массиве M 3 будут последовательно записаны 12 коэффициентов многочлена T (x), начиная с T₀ и кончая T₁₁. Если K не равно 0, то осуществляется переход к оператору 2 и происходит вычисление очередного коэффициента. В результате осуществления описанного алгоритма в массиве M 3 будут записаны R = S коэффициентов модифицированного синдромного многочлена T(x) по адресам (A₃ + 1) - (A₃ + R - S).

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

Коэффициенты этого многочлена определяются с использованием произведения T(x)·σ(x) аналогично тому, как это было сделано при вычислении коэффициентов модифицированного синдромного многочлена.

Система уравнений для определения коэффициентов σ_t имеет вид
,
(аналогично [7], с. 171, формула Б 14).

Эта система уравнений может решаться, например, методом Гаусса [13] путем сведения матрицы коэффициентов к треугольной форме.

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

На фиг. 19 в качестве примера приведен алгоритм определения коэффициентов многочлена σ(x) для случая исправления двух ошибок, то есть t=2.

Матрица коэффициентов будет иметь вид
.

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

В операторе A2

В операторе A4

В операторе A6

В операторе A8

В операторе A9 определяются σ₁ и σ₂ .

В операторе B2 осуществляется перестановка строк.

В операторе B33

В операторе B6

Анализ выражений (24 - 30( показывает, что в них участвуют только три операции: деления, сложения по модулю два и умножения.

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

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

В пятой процедуре находятся локаторы ошибок х_j путем решения уравнения (21). В общем случае это уравнение может решаться путем последовательной подстановки в это уравнение всех локаторов кода и выбора в качестве решения тех локаторов, при которых уравнение обращается в ноль (процедура Ченя, см. [7], с. 176).

Для t≅4 можно воспользоваться алгоритмом решения, изложенным в [12, с. 58 - 65]. Например, для t=3 уравнение (21) приводится к виду

которое решается табличным путем: путем считывания из ПЗУ по адресу, соответствующему свободному члену уравнения корней Z₁ и Z₂, причем Z₃=Z₁+Z₂, и последующего определения локаторов ошибок из выражения
.

Предлагаемое устройство реализует операцию возведения в степень : нахождения величины σ²₁ в (31) путем умножения элемента самого на себя, операцию деления в (30) путем умножения на обратный элемент, как в предыдущей процедуре. Операция извлечения квадратного корня в предлагаемом устройстве реализуется табличным путем, для чего в ПЗУ блока памяти записана таблица квадратных корней элементов поля GF(2⁸). Значение (σ²₁ + σ₂)^0,5 в (31) находится путем считывания из этой таблицы по адресу (σ²₁ + σ₂) .

Остальные операции в (31) и (30) являются операциями сложения по модулю два. Ввиду известности выполнения операций из описания работы устройства детальное описание алгоритма вычисления по выражению (31) не приводится.

После определения локаторов (номеров позиций) ошибок стирания ошибки объединяются в одно понятие: искажения.

В шестой процедуре вычисляется многочлен локаторов искажений, который имеет вид

Алгоритм определения коэффициентов многочлена искажений совпадает с алгоритмом определения коэффициентов многочлена стираний и является его продолжением.

Пусть, например, S=3 и t=2. Тогда в массиве M 2 (фиг. 17) будут записаны шесть коэффициентов, три из которых являются коэффициентами λ₁, λ₂, λ₃ уравнения (7) и три λ⁽₁²⁾, λ⁽₁³⁾, λ⁽₂³⁾ - промежуточными коэффициентами.

Выражения для нахождения следующих коэффициентов λ₄ и λ₅ уравнения (32) будут иметь вид

Выражения для промежуточных коэффициентов будут иметь вид

В результате выполнения алгоритма эти коэффициенты будут записаны в массив M 2 по адресам (A₂+7) - (A₂+15).

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

Для определения (S+t)-го искажения используется формула, соответствующая алгоритму Форни (см. [6], с. 219, рис. 77, формула для определения Y_l, при этом следует учесть, что использование обратных элементов X^-_l¹ эквивалентно использованию прямых элементов), которая в обозначениях, принятых в материалах заявки, имеет вид

где
λ_s+t-1- λ₁ - коэффициенты многочлена искажений λ(x) (формула 7), определенные в шестой процедуре;
S_o - S_s+t-1 - первые (S+t) коэффициенты синдромного многочлена S(x) (формула 6), определенные в первой процедуре обобщенного алгоритма;
λʹ(x_s+t) - значение производной многочлена λ(x), полученное при подстановке в λʹ(x) значения x = x_s+t.

Производная многочлена λ(x) вычисляется по формулам
для четного S
λʹ(x) = [(λ₁·x²+ λ₃)x²+ λ₄]x²+...+λ_s+t-1; (36)
для нечетного S
λʹ(x) = [(x²+ λ₂)x²+ λ₄]x²+...+λ_s+t-1. (37)
Вычисление производной целесообразно осуществлять на этапе вычисления коэффициентов многочлена локаторов стираний.

Ввиду того, что вычисления λʹ(x) происходит по формуле Горнера [4], детальное описание алгоритма не приводится.

Подставляя в формулу (35) известные значения коэффициентов получим значение последнего искажения E_S+t , соответствующего локатору x_s+t.

Исправление искаженного символа осуществляется путем его суммирования с вектором ошибки.

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

При i = 1 определяется синдромный многочлен, соответствующий откорректированному последнему искажению, после чего по выражению (35) находится предпоследний вектор искажения. Повторяя этапы вычисления векторов E_s+t-(i-1) и соответствующих им синдромных многочленов, на последних этапах получаем

Занчения векторов ошибок записываются в один из РОНов микропроцессора. Затем по адресу искаженного символа, определяемому его локатором, осуществляются исправление искаженного символа путем суммирования его с вектором ошибки и запись результата сложения на место искаженного символа.

Число команд, необходимое для декодирования блока каскадного кода, является переменной величиной и зависит от числа ошибок и стираний в блоке. Для наиболее тяжелого случая, когда исправляется 16 стираний, для декодирования внешнего (241, 225) кода потребуется 1,37 команды на бит, для декодирования внутреннего (24, 16) когда потребуется 0,86 команды на бит. Полное декодирование блока каскадного кода осуществляется за ≃ 13000 команд, что составляет 2,23 команды на бит.

Таким образом, предлагаемое техническое решение позволяет осуществить операции кодирования и декодирования информации как обычными двоичными, так и недвоичными кодами. Особенно эффективным является применение каскадного кодирования, которое при равной скорости передачи информации позволило получить выигрыш в помехоустойчивости, равный 2 дБ (каскадный код: РС и короткий блоковой код), по сравнению с двоичным блоковым кодом (жесткое решение) [14, с. 320, таблица 8.1], и даже еще больший выигрыш при использовании M-ичной модуляции [14, с. 322, таблица 8.2].

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

Оптимальное сочетание аппаратных и программных средств в устройстве позволило обеспечить высокую скорость обработки информации, составляющую в режиме кодирования около 1,66 и в режиме декодирования 2,23 команды на бит (в сумме 3,89 команды на бит), что свидетельствует о значительном выигрыше предлагаемых процедур кодирования и декодирования по сравнению с результатами, достигнутыми в [15], где скорость кодирования-декодирования только кода РС составляет 800 команд/бит.

Применение более высокоскоростных процессоров, например Intel 80386, позволит уменьшить время кодирования и декодирования не менее чем в 50 раз.

Источники информации.

1. Авт. св. N 1275782, кл. H 03 M 13/02, 1986.

2. Авт. св. N 1309317, кл. H 03 M 13/02, 1987.

3. Авт. св. N 1481902, кл. H 03 M 13/00, 1988.

4. Авт. св. N 1635193, кл. H 06 M 15/31.

5. Авт. св. N 1418913, кл. H 03 M 13/00, 1988 (прототип).

6. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

7.Форни Д. Каскадные коды. М.: Мир, 1970.

8. Хвощ С.Т., Варлинский Н.Н., Попов Е.А. Микропроцессоры и микроЭВМ в системах автоматического управления. Справочник. Л.: Машиностроение, 1987.

9. Цифровые и аналоговые интегральные микросхемы. Справочник. М.: Радио и связь, 1990.

10. Истомин Г. С., Парижская И.С. Об использовании микроЭВМ для реализации арифметических операций в полях Галуа. Техника средств связи, серия ТПС, вып. 2, 1978.

11. В.О.Шварцман, Г.А. Емельянов. Теория передачи дискретной информации. М.: Связь, 1979, с. 318.

12. Э. М. Габидулин, В.Б.Афанасьев. Кодирование в радиоэлектронике. М: Радио и связь, 1986.

13. Сигорский В.П. Математический аппарат инженера. Киев: Техника, 1977, с. 230.

14. Дж. Кларк, мл, Дж. Кейм. Кодирование с исправлением ошибок в системах цифровой связи. М.: Радио и связь, 1986.

15. Микропроцессорные кодеры и декодеры. М.: Радио и связь, 1991, с. 86.

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10, Рисунок 11, Рисунок 12, Рисунок 13, Рисунок 14, Рисунок 15, Рисунок 16, Рисунок 17, Рисунок 18, Рисунок 19