СПОСОБ КОДИРОВАНИЯ ИНФОРМАЦИИ ОТРЕЗКАМИ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
METHOD OF ENCODING INFORMATION WITH SECTIONS OF LINEAR RECURRENT SEQUENCES

Способ кодирования информации отрезками линейных рекуррентных последовательностей предназначен для кодирования дискретных сообщений и может быть использован как в синхронных, так и в асинхронных системах для передачи информации по каналам связи с сохранением высокой достоверности.
Изобретение относится к радиотехнике, а именно к способам кодирования дискретной информации, и предназначено для кодирования дискретной информации с высокой достоверностью. Написано на основании индекса МПК H04L 17/00.
В области передачи дискретной информации существует проблема, разработки способов помехоустойчивого кодирования информации на основе линейных рекуррентных последовательностей. В качестве аналога способа используется устройство для передачи и приема дискретной информации (авт. св. СССР №642867, H04L 17/00, опубл. 1979 г.).
Недостатками данного устройства являются сравнительно высокая вероятность ложного декодирования, подверженность размножению ошибок на каналах связи с помехами, зависимость эффективности кодирования от помехоустойчивости.
Устройство для передачи и приема дискретной информации содержит на передающей стороне регистр сдвига с цепью обратной связи, а на приемной стороне - первый регистр сдвига с цепью обратной связи, между входом и соответствующим выходом которого включен сумматор по модулю два, второй регистр сдвига с цепью обратной связи, счетчик и триггер управления, а также на передающей стороне - вычитающий счетчик, дешифратор, инвертор, триггер, блок совпадения, элемент ИЛИ и блок задержки, при этом выходы вычитающего счетчика подключены к соответствующим входам дешифратора, выход которого непосредственно и через инвертор подключен к входам триггера, выход которого через последовательно соединенные блок совпадения и элемент ИЛИ подключен к тактовому входу регистра сдвига с цепью обратной связи, выход которого подключен к входу блока задержки, а на приемной стороне - блок сравнения, инвертор, блок задержки, блок совпадения, элемент ИЛИ, суммирующий счетчик и промежуточный накопитель, при этом выход сумматора по модулю два подключен через инвертор к счетному входу счетчика, к входу "Сброс" которого подключены выход сумматора по модулю два и выход счетчика через блок задержки, между выходами соответствующих разрядов первого и второго регистров и сдвига с цепями обратной связи включен блок сравнения, выход которого подключен к нулевому входу триггера управления, к единичному входу которого подключен выход счетчика, а выходы триггера управления подключены к входам суммирующего счетчика непосредственно и через блок совпадения, выход которого подключен к соответствующему входу второго регистра сдвига с цепью обратной связи через элемент ИЛИ, а выходы суммирующего счетчика подключены к соответствующим входам промежуточного накопителя, блок сравнения состоит из сумматоров, к входам которых подключены второй регистр сдвига с цепью обратной связи, а к входам - первый регистр сдвига с цепью обратной связи элемента ИЛИ и инвертора, кроме того, на чертеже показаны входы вычитающего счетчика, входы и блока совпадения, вход элемента ИЛИ для подачи "быстрых" тактовых импульсов входы и элемента ИЛИ, входы блока совпадения и канал связи между передающей и приемной сторонами.
Задачей изобретения является разработка способа помехоустойчивого кодирования дискретной информации, позволяющего передавать информацию с высокой достоверностью.
Эта задача решается тем, что способ кодирования информации основывается на преобразовании кодируемой информации в фазовые соотношения двух отрезков рекуррентных последовательностей (РкП) на передаче и обратных преобразованиях на приеме.
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного способа кодирования дискретной информации, отсутствуют, что указывает на соответствие изобретения условию патентоспособности «новизна».
Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного изобретения, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, изобретение соответствует условию патентоспособности «изобретательский уровень».
Заявленный способ поясняется чертежами, на которых показаны:
фиг. 1 - схема умножения элементов поля;
n
фиг. 2 - техническая реализация модуля вычисления состояния ПГРС на базе однотактового умножителя элементов поля GF(2);
фиг. 3 - этапы процесса кодирования информации отрезками линейных рекуррентных последовательностей;
фиг. 4 - структурная схема реализуемого способа;
фиг. 5 - график зависимости вероятности ложного декодирования информации от коэффициента ошибки в канале связи для прототипа;
фиг. 6 - график зависимости вероятности ложного декодирования информации от коэффициента ошибки в канале связи для прототипа.
Реализация заявленного способа кодирования дискретной информации заключается в следующем.
1
2
Каждый отрезок РкП несет в себе информацию о синхронном преобразовании двух простых генераторов на регистрах сдвига (ПГРС) при одинаковом начальном состоянии, имеющих разные характеристические полиномы P(x), P(x) и одинаковую разрядность n (фиг. 3).
Для сохранения синхронности преобразований в случае последовательной передачи двух отрезков РкП вычисляются начальные состояния этих ПГРС, исходя из кодируемой информации, очередности передачи отрезков РкП по каналу, их величины и выбора участка на М-последовательности.
01
1
1
01
02
2
2
02
01
02
2
1
n
Для обеспечения эффективности кодирования информации выбирается участок в конце М-последовательностей величиной (3÷5)n≥N-m>n и (3÷5)n≥N-m>n, где n и n длина "скользящего окна" на РкП1 и РкП2 соответственно, N=N=2-1.
1
1
1
2
2
2
1
1
2
2
Если передается отрезок РкП1 первым, а РкП2 следом за ним, то для обеспечения синхронной обработки отрезков анализаторами на приеме необходимо, чтобы на РкП1 выбирался отрезок [N-m;N-m], а на РкП1 отрезок [N-m; 0], причем N-m=2(N-m).
n
Информация, поступающая от источника в двоичном виде, записывается в два умножителя произвольных элементов поля GF(2).
0
1
n-1
0
1
2
n-1
1
1
1
2
2
2
n-1
a
a
a
a
Каждый из умножителей выполняет операцию вычисления двоичной комбинации c+cε+…+cε, полученной из начальной [, , , …, ] за один такт его работы так, если бы производился сдвиг этой комбинации в ПГРС на заданное количество j тактов. Для ПГРС1, j=N-m, а для ПГРС2, j=N-m.
i
j
n
Для реализации вычисления необходимой комбинации выбирается один произвольный элемент ε и один постоянный ε, принадлежащие полю GF(2). Выражаются эти элементы поля через левый степенной базис следующим образом:
i
n-1
n
a
a
a
a
0
1
n-1
i
ε=+ε+…+ε, ∈GF(2),
j
k-1
n
0
1
k-1
j
ε=b+bε+…+bε, b∈GF(2),
Тогда произведение этих элементов
i
j
i+j
k-1
n
0
1
n-1
i
ε*ε=ε=c+cε+…+cε, c∈GF(2),
0
1
n-1
0
1
2
n-1
n-1
a
a
a
a
Процесс вычисления c+cε+…+cε может быть реализован в матричной форме как произведение вектора [, , , …, ] на сопровождающую F матрицу в j-й степени (фиг. 1).
Схема умножения элементов поля представлена на фиг. 1.
Техническая реализация модуля вычисления на базе однотактового умножителя представлена на фиг. 2.
Преимуществом данной схемы является его быстродействие - требуется всего один такт для сдвига исходной комбинации в ПГРС на заданное количество j тактов.
2
n
n
Тем не менее, при длине ПГРС n необходимо n схем однотактовых умножителей элементов поля GF(2). При большом n модуль вычисления состояния ПГРС необходимо производить на базе n-тактового умножителя элементов поля GF(2), требующий для своей реализации 3n ячеек памяти, n схем совпадения и n+(ω-2) сумматоров по mod2, где ω - число ненулевых слагаемых многочлена Р(х).
Для задания цикла работы кодера на передаче в его состав включен формирователь цикловой частоты, который через устройство управления пуском ПГРС обеспечивает начало и окончание передачи отрезков РкП1 и РкП2 последовательным кодом поочередно.
1
2
На приеме отрезки РкП1 и РкП2 одновременно поступают на входы двух анализаторов ПГРС (АПГРС), обрабатывающих последовательности по закону характеристических полиномов Р(х) и Р(х) соответственно. В анализаторах происходит опознавание принятых отрезков РкП по безошибочному "скользящему" участку (фигура 3).
<mrow><msub><mi>t</mi><mi>ц</mi></msub><mo>=</mo><mfrac><mrow><msub><mi>N</mi><mn>2</mn></msub><mo>−</mo><msub><mi>m</mi><mn>2</mn></msub></mrow><mrow><msub><mi>V</mi><mrow><mi>п</mi><mi>е</mi><mi>р</mi></mrow></msub></mrow></mfrac></mrow>
авт
пер
В случае выделения безошибочного "скользящего окна" двумя АПГРС они последовательно отключаются от канала связи, переходят в автономный режим работы, сохраняя при этом синхронность обработки информации, и если в течение времени
схемой сравнения обнаружится совпадение состояний АПГРС1 и АПГРС2, то через устройство управления выводом информации открывается клапан и обеспечивается считывание информации с АПГРС1 параллельным кодом за один такт в буферный накопитель (БН) приема, осуществляется запуск формирователя цикловой частоты. Первый импульс цикловой частоты устанавливает и подключает входы АПГРС1 и АПГРС2 к КС, на вход ОЛЗ на К тактов записывается логическая "1". Величина ОЛЗ на К тактов определяет допустимое время t автономного поддержания синхронизма декодера с кодером, которое определяется скоростью передачи V, стабильностью опорных генераторов кодера и декодера.
авт
Если в течение t будет успешно принят очередной блок информации, то произойдет стирание логической "1" в ОЛЗ на K тактов, и на его вход запишется новая "1" очередным импульсом цикловой частоты с формирователя цикловой частоты.
авт
Если в течение t не будет принят очередной блок информации, то с выхода ОЛЗ на K тактов логическая "1" остановит выработку цикловой частоты приема формирователем и включит в работу устройство управления АПГРС.
<mrow><msub><mi>t</mi><mrow><mi>о</mi><mi>ж</mi></mrow></msub><mo>=</mo><mn>1,5</mn><mfrac><mrow><msub><mi>N</mi><mn>2</mn></msub><mo>−</mo><msub><mi>m</mi><mn>2</mn></msub><mo>−</mo><msub><mi>n</mi><mrow><mn>02</mn></mrow></msub></mrow><mrow><msub><mi>V</mi><mrow><mi>п</mi><mi>е</mi><mi>р</mi></mrow></msub></mrow></mfrac></mrow>
ож
В этом случае при выделении безошибочного "скользящего окна" первым АПГРС устройство управления АПГРС перейдет в режим "ожидания" выделения безошибочного "скользящего окна" на втором АПГРС в течение
. По истечении времени ожидания устройство управления АПГРС установит анализаторы в исходное состояние. При выделении "скользящего" окна в АПГРС2 за t выключится устройство управления АПГРС и декодер перейдет в основой режим работы и запустит формирователь цикловой частоты.
В случае выделения безошибочного "скользящего окна" вторым АПГРС и не выделения безошибочного "скользящего окна" первым АПГРС устройство управления АПГРС немедленно переведет анализаторы в исходное состояние.
Структурная схема реализуемого способа представлена на фиг. 4.
Достоинствами рассматриваемого способа кодирования информации является:
- высокая помехоустойчивость, определяемая возможностью выбора размера "скользящего окна", сравнимого с длиной ПГРС, и длины отрезка линейной рекуррентной последовательности, позволяющие находить необходимое соотношение между помехоустойчивостью и эффективностью кодирования;
- предельно малая вероятность приема ложной информации за счет того, что при обработке (декодировании) одного сообщения на приеме в течение одного цикла в множестве разрешенных комбинаций будет только одна комбинация, появление которой ожидается в жестко определенном интервале времени и только один раз. Это объясняется тем, что информационный блок определяет начальное состояние двух ПГРС и такое состояние может встретиться в каждом цикле только один раз при обработке отрезков линейной рекуррентной последовательности на приеме;
- способ кодирования информации обеспечивает самосинхронизацию в процессе передачи и приема информации, а также возможность применения данного способа как в синхронных, так и в асинхронных системах передачи данных.
Промышленная применимость изобретения обусловлена тем, что устройство, реализующее предложенный способ, может быть осуществлено с помощью современной элементной базы, с достижением указанного в изобретении назначения. Заявленный способ кодирования дискретной информации обеспечивает передачу информации с высокой достоверностью.
Показатели предложенной системы кодирования зависят от вероятности правильного выделения безошибочных "скользящих окон" на приеме.
Тогда полная группа событий при декодировании информации определяется выражением
пдк
лдк
прс
Р+Р+Р=1
пдк
лдк
прс
где Р - вероятность правильного декодирования информации; Р - вероятность ложного декодирования информации; Р - вероятность не приема (пропуска) декодируемой информации.
лдк
прс
пдк
Уменьшение величины одного из слагаемых - Р или Р ведет к увеличению значения Р и повышению помехоустойчивости систем кодирования.
Для разрабатываемого способа вероятность ложного декодирования информации определяется как
ск.ок
0
0
где Р - вероятность выделения "скользящего окна", n=n+m, где n - длина ЛРР, m - величина счетчика совпадений.
Для прототипа вероятность ложного декодирования информации определяется как:
лдк
ск.ок
но
Р=1-(Р-N·Р)
Результаты моделирования представлены на фиг. 5 и 6 в виде графиков зависимостей вероятностей ложного декодирования информации от коэффициента ошибки в канале связи для прототипа (фиг. 5) и предлагаемого способа (фиг. 6) при n=7.