Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов

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

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Управляющие системы и машины
Дата:	2015
Автор:	Завадский, И.А.
Формат:	Стаття
Мова:	Російська
Опубліковано:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2015
Теми:	Проблемы информационного пространства и информационной безопасности
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/87176
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов / И.А. Завадский // Управляющие системы и машины. — 2015. — № 1. — С. 25–31. — Бібліогр.: 4 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859649907425542144
author	Завадский, И.А.
author_facet	Завадский, И.А.
citation_txt	Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов / И.А. Завадский // Управляющие системы и машины. — 2015. — № 1. — С. 25–31. — Бібліогр.: 4 назв. — рос.
collection	DSpace DC
container_title	Управляющие системы и машины
description	Предложен метод повышения эффективности сверточных помехоустойчивых кодов без увеличения вычислительных затрат на кодирование и декодирование. Сверточные коды рассматриваются как частный случай более общей схемы, где кодирование и декодирование выполняются конечным автоматом определенной структуры. Метод позволяет почти вдвое повысить уровень помехоустойчивости лучшего из известных сверточных кодов. The method of the convolutional codes empowering without increasing the computational complexity is presented. The convolutional code is considered as a partial case of more general schema where decoding and encoding are performed by a finite automaton of the certain structure. The proposed method outperforms the best convolutional code of the same graph size almost twice, having the same computational complexity. Запропоновано метод підвищення ефективності згорткових завадостійких кодів без збільшення обчислювальних витрат на кодування та декодування. Згорткові коди розглядаються як окремий випадок більш загальної схеми, де кодування та декодування виконуються скінченним автоматом певної структури. Метод дає змогу майже вдвічі покращити показники завадостійкості найкращого згорткового коду.
first_indexed	2025-12-07T13:32:33Z
format	Article
fulltext	УСиМ, 2015, № 1 25 Проблемы информационного пространства и информационной безопасности УДК 519.725 И.А. Завадский Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов Предложен метод повышения эффективности сверточных помехоустойчивых кодов без увеличения вычислительных затрат на кодирование и декодирование. Сверточные коды рассматриваются как частный случай более общей схемы, где кодирование и декодирование выполняются конечным автоматом определенной структуры. Метод позволяет почти вдвое повысить уровень помехоустойчивости лучшего из известных сверточных кодов. The method of the convolutional codes empowering without increasing the computational complexity is presented. The convolutional code is considered as a partial case of more general schema where decoding and encoding are performed by a finite automaton of the certain structure. The proposed method outperforms the best convolutional code of the same graph size almost twice, having the same computational complexity. Запропоновано метод підвищення ефективності згорткових завадостійких кодів без збільшення обчислювальних витрат на ко- дування та декодування. Згорткові коди розглядаються як окремий випадок більш загальної схеми, де кодування та декоду- вання виконуються скінченним автоматом певної структури. Метод дає змогу майже вдвічі покращити показники завадостій- кості найкращого згорткового коду. 1 Ключевые слова: конечный автомат, помехоустойчивый код, сверточный код. Введение. Сверточные коды – это один из наи- более изученных и широко используемых мето- дов помехоустойчивого кодирования. Коды про- сты в реализации, но эффективность даже самых лучших кодов этого класса далека от теоретиче- ского предела Шеннона [1]. Поэтому в послед- нее десятилетие во многих практических прило- жениях предпочтение отдается более мощным кодам с низкой плотностью проверок на чет- ность (LDPC-кодам) [2] и турбо-кодам [3]. Од- нако высокая эффективность упомянутых поме- хоустойчивых кодов достигается не «бесплатно»: LDPC-коды эффективны только при достаточно больших длинах блоков входных данных, а тур- бо-коды представляют собой многоуровневую схему, на каждом уровне которой реализован некий базовый, более простой код (который мо- жет быть в частности сверточным кодом), а зна- чит, и вычислительная сложность кодирования и декодирования для турбо-кодов будет сущест- венно выше, чем для базовых сверточных кодов. В данной статье приведен метод повышения эффективности сверточных кодов, не требую- щий дополнительных вычислительных затрат. Как известно, любой сверточный код может быть сгенерирован конечным автоматом спе- циального вида, удовлетворяющим определен- ным ограничениям на количество состояний, количество переходов из каждого состояния и пр. Идея метода состоит в том, чтобы рассмат- ривать в качестве генераторов кода более ши- рокий класс конечных автоматов, что, возмож- но, позволит получить код с лучшими помехо- устойчивыми свойствами. При этом, как пока- зано далее, вычислительная сложность коди- рования и декодирования не повышается. Постановка задачи Исследуем свойства конечных автоматов, по- зволяющих генерировать эффективные поме- хоустойчивые коды, т.е. коды, существенно снижающие вероятность ошибки на бит при передаче сообщений по каналу связи с поме- хами. С этой целью следует описать метод ко- 26 УСиМ, 2015, № 1 дирования посредством конечных автоматов общего вида, метод декодирования, алгоритм построения эффективных кодирующих авто- матов, а также методы определения важней- ших характеристик кодов, генерируемых ко- нечными автоматами. Помехоустойчивое кодирование с исполь- зованием конечных автоматов Рассмотрим конечный автомат, из каждого состояния которого существует 2k переходов в другие состояния. Предположим, что перехо- ды выбираются исходя из значения k двоичных символов входной последовательности битов и на каждом переходе автомат генерирует t би- тов кодового слова, где k < t. Таким образом код, генерируемый автоматом, будет иметь скорость k / t. Например, на рис. 1 изображен автомат с четырьмя состояниями, генерирую- щий код скорости которого ½. Входные сим- волы записаны над стрелками переходов перед косой чертой, а генерируемые – после косой. Предположим также, что состояния автомата пронумерованы и он начинает работу в со- стоянии ноль. 1 2 0 3 0/00 1/11 1/11 0/010/00 1/10 1/10 0/01 Рис. 1. Автомат, генерирующий код скорости которого ½ Одна из существенных характеристик каче- ства кода это dmin – минимальное расстояния Хэмминга между кодовыми словами. Опишем метод вычисления величины dmin для кода, ге- нерируемого конечным автоматом. Примем, что есть конечный автомат с n вершинами, а F – квадратная матрица, строки и столбцы которой пронумерованы парами индексов ij: 0 ≤ i < n, i ≤ j < n. Рассмотрим два экземпляра автомата, один из которых находится в состоянии i, а другой – в состоянии j. Допустим, что через одну итерацию автоматы перейдут в состояния p и k, причем какой из экземпляров автомата в какое именно перейдет состояние – несуще- ственно. Элементу fij,kp матрицы F присвоим минимальное расстояние Хэмминга между сло- вами, которые могут быть сгенерированы ав- томатами при таких переходах. Если из со- стояний і и j в состояния p и k перейти невоз- можно или если i = j и p = k, будем считать, что элемент fij,kp равен некоторому достаточно большому числу M. Так, для изображенного на рис. 1 автомата матрица F показана в табл. 1 (сначала записаны строки и столбцы ij с раз- личными значениями i и j). Т а б л и ц а 1. Матрица минимальных расстояний Хэмминга между кодовыми словами, генерируемыми ко- нечным автоматом 01 02 03 12 13 23 00 11 22 33 01 M 1 1 1 1 M M M M M 02 0 M M M M M M 2 M M 03 M 1 1 1 1 M M M M M 12 M M M 1 1 M M M M M 13 M M M M M 0 M M 2 2 23 M M M 1 1 M M M M M 00 2 M M M M M M M M M 11 M M M M M 2 M M M M 22 M M M M M M M M M M 33 M M M M M 2 M M M M Рассмотрим над множеством целых чисел поле, в котором операцией « + » будем считать поиск минимума, а операцией « * » – сложе- ние, причем предположим, что для любого чис- ла a выполняется равенство M*a = M. Над мат- рицами, элементы которых принадлежат этому полю, определена операция умножения и, как можно отметить, в матрице Fd элемент с индек- сами ij,kp будет равен минимально возможно- му расстоянию Хэмминга между словами, гене- рируемыми за d переходов двумя экземпляра- ми автомата, которые начинают работу в состо- яниях i и j и заканчивают в состояниях k и p. Очевидно, что минимальное расстояние Хэмминга между генерируемыми автоматом кодовыми словами равно минимальному, по всем возможным комбинациями i и j, расстоя- нию Хэмминга между различными словами, которые могут быть сгенерированы за одно и то же количество итераций двумя экземпляра- ми автомата, начинающими работу в одном и том же состоянии i и заканчивающими ее в од- ном и том же состоянии j, т.е. эта величина равна минимальному среди элементов fii,jj в матрицах F, F2, F3 и т.д. Так, для изображен- ного на рис. 1 автомата, матрица F которого УСиМ, 2015, № 1 27 приведена в табл. 1, все элементы матриц F и F2 с индексами ii,jj равны M, в матрице F3 они равны пяти, в матрице F4 – шести, а начиная с матрицы F4 – семи и более. Поэтому величина dmin для кода, генерируемого таким автоматом, составляет пять. Легко показать, что для определения dmin для генерирующего код автомата с n вершина- ми достаточно рассмотреть матрицы Fd, где d ≤ n2. Действительно, обозначим через H(a, b,… ; x, y,…) расстояние Хэмминга между кодо- выми словами, генерируемыми двумя экземп- лярами автомата, один из которых проходит че- рез состояния a, b, …, а другой – через состоя- ния x, y, …, и предположим, что dmin = H(i1, … ,id ; j1, …, jd), где d > n2, i1 = j1, id = jd. По- скольку существует всего n возможных значе- ний it и jt, то существует не более n2 различных пар (it , jt), а значит, для некоторых значений k и t, таких, что 1 ≤ k < t < d, будет выполняться равенство (ik , jk) = (it , jt) и существуют пути через состояния i1, …, ik, it+1, …, id и j1, …, jk, jt+1, …, jd, длина которых меньше d. Но, так как H(ik, …, it ; jk, …, jt) ≥ 0, то H(i1, …, ik, it+1, …, id ; j1, …, jk, jt+1, …, jd) ≤ H(i1, …, id ; j1, …, jd) = dmin, а зна- чит, dmin достигается на путях, которые короче d. Декодирование Для декодирования сгенерированного авто- матом кода можно применять те же методы, что и для сверточных кодов, наиболее извест- ный из которых – метод Витерби. Он предпо- лагает осуществление двух проходов: прямого и обратного. На i-й итерации прямого прохода каждому из состояний j, в которых может пре- бывать автомат после i-го перехода, приписы- вается метрика j im . Рассматривая двоичную фазовую модуляцию в канале с аддитивным гауссовым белым шумом (АГБШ) [4], и коди- руя нулевой бит как сигнал 1, а единичный бит – как сигнал –1, будем вычислять метрику по формуле   1min , j j k i i kj ik K m m s r    . (1) Через Kj обозначено множество состояний, из которых существуют переходы в состояние j, skj – строка из t символов, записываемых ав- томатом в кодовое слово на переходе из k-го состояния в j-е, ri – набор из t действительных чисел – сигналов на входе декодера, соответ- ствующих i-му переходу, а     1 , , t p p kj i p kj i p s r s r     , где       2 ' ' 2 ' ' 1 , если 0 ; , 1 , если 1. p p i kjp p t kj i p p i kj r s s r r s         Предположим, что при декодировании, как и при кодировании, автомат начинает работу в состоянии ноль, и будем считать, что 0 0 0m  . На обратном проходе реконструируется путь из состояний автомата, от последнего к перво- му. Сначала выбираем состояние с минималь- ной метрикой, полученной на последней ите- рации прямого прохода, а затем придержива- емся следующего принципа: если на шаге i было реконструировано состояние j, то на ша- ге i – 1 выбираем состояние k, минимизирую- щее метрику j im в формуле (1). Построение эффективных кодирующих автоматов В дальнейшем будем рассматривать только автоматы, генерирующие код скорости ½, одна- ко все изложенные результаты могут быть легко обобщены и для других разновидностей автома- тов, генерирующих помехоустойчивые коды. Рассмотрим влияние структуры графа конеч- ного автомата на качество генерируемого им кода. Как отмечено ранее, одна из важнейших характеристик качества кода – dmin – мини- мальное расстояние Хэмминга между кодовы- ми словами, которое можно определить как ми- нимальное расстояние Хэмминга между слова- ми, генерируемыми автоматом при проходе различными путями одинаковой длины из не- которого состояния a в некоторое состояние b. Если в ориентированном графе автомата суще- ствует два различных пути одинаковой длины m из состояния a в состояние b, будем назы- вать их двойным путем длины m. Докажем следующий факт. Лемма 1. Граф автомата, генерирующего код скорости ½ и имеющего n состояний, содержит 28 УСиМ, 2015, № 1 по крайней мере один двойной путь длины 2log 1n   . Доказательство. Если автомат генерирует код скорости ½, то в каждом состоянии он считывает один бит исходного кода и, в зави- симости от его значения, записывает два бита в кодовое слово и переходит в одно из двух дру- гих состояний. Таким образом, из каждой вер- шины графа этого автомата исходит две дуги. Предположим, что все вершины графа прону- мерованы и обозначим через am список из 2m номеров вершин (возможно, повторяющихся), в которые из вершины a ведут пути длины m. Если некоторый номер встречается в списке am более одного раза, то это означает, что граф содержит двойной путь длины m. Список 2log 1na  содержит более n элементов и, так как всего в рассматриваемом графе n вершин, то элементы этого списка будут повторяться, из чего и следует утверждение леммы. Чем выше значение dmin, тем большее коли- чество ошибок в кодовых словах заданной длины можно исправлять. Поскольку при каж- дом переходе рассматриваемые автоматы за- писывают в код на выходе два бита, то при на- личии в графе автомата двойного пути длины m величина dmin генерируемого им кода не мо- жет превышать 2m. Поэтому, если рассматри- вать только структуру графа, из двух автома- тов лучшим можно считать тот, в графе кото- рого длина самого короткого двойного пути бу- дет большей. С учетом леммы 1 среди автома- тов с n состояниями наилучшими будут те, гра- фы которых не содержат двойных путей длиной 2log n  или более коротких. В лемме 2 сфор- мулируем принцип построения графа с 2m вер- шинами, удовлетворяющего этому свойству, т.е. не содержащего двойных путей длиной m или более коротких. Лемма 2. Предположим, что граф имеет 2m вершин, пронумерованных от нуля до 2m – 1 и из каждой вершины выходят две дуги, причем если 0 ≤ i ≤ 2m–1 – 1, то дуги ведут в вершины 2i и 2i + 1, а если 2m–1 ≤ i < 2m – то в вершины 2i – – 2m и 2i – 2m + 1. Тогда граф не содержит двойных путей длиной меньше m + 1. Доказательство. Возьмем произвольную вер- ину с номером i и рассмотрим представление этого номера в двоичном виде. Если i ≤ 2m–1 – 1, то из этой вершины за один шаг можно перей- ти к вершинам 2i и 2i + 1, 2i – 2m или 2i – 2m + 1. Переход к вершине 2i означает сдвиг двоично- го представления номера i влево на один бит, а переход к вершине 2i + 1 – сдвиг влево на один бит с последующей инверсией самого младше- го бита. Если же i ≥ 2m–1, то за один шаг можно перейти к вершине 2i – 2m, что означает сдвиг номера вершины влево на один бит и инвер- сию самого старшего бита либо к вершине 2i – – 2m + 1, что эквивалентно сдвигу влево на один бит с последующей инверсией самого старше- го и самого младшего битов. Таким образом, при любом переходе самый младший бит в двоичном представлении номера вершины i сместится влево на одну позицию, но его зна- чение при этом не изменится. Более того, его значение не изменится и на m – 1 в последую- щих переходах, пока он не станет самым стар- шим, т.е. m + 1. Теперь заметим, что самые младшие биты номеров вершин, в которые ве- дут дуги из некоторой вершины i, всегда раз- личны. Поэтому будут различны и вторые би- ты номеров вершин, к которым существуют различные пути из вершины i длиной два, тре- тьи биты номеров вершин, к которым сущест- вуют различные пути из вершины i длиной три и т.д. Таким образом, из произвольно выбран- ной вершины i невозможно перейти в одну и ту же другую вершину j различными путями, длина которых меньше m + 1. Лемма доказана. Заметим, что граф автомата с четырьмя вер- шинами, изображенный на рис. 1, удовлетво- ряет сформулированному в лемме 2 принципу. Легко проверить, что он не содержит двойных путей длины меньше трех. Лемма 3 устанавливает взаимосвязь между графами описанной в лемме 2 структуры и диаграммами состояний сверточных кодов. Лемма 3. Вершины графа диаграммы со- стояний любого несистематического сверточ- ного кода скорости ½, обладающего памятью m, могут быть пронумерованы так, чтобы вы- полнялось условие леммы 2. УСиМ, 2015, № 1 29 Доказательство. Устройство, генерирую- щее указанный в условии леммы сверточный код, на каждой итерации считывает из входя- щего сообщения m двоичных символов, кото- рые обозначим xt, …, xt+m–1, и вычисляет зна- чения двух линейных функций: 1 2 1 2 1 2 ... , ... . k l i i i j j j y x x x y x x x         Здесь t ≤ iq ≤ t + m – 1, t ≤ jq ≤ t + m – 1. Би- ты y1 и y2 записываются в код на выходе. На следующей итерации кодирующее устройство считывает символы xt+1, …, xt+m, вновь вычис- ляет по ним эти же линейные функции (с соот- ветствующим сдвигом индексов аргументов), записывает два бита в код на выходе и т.д. Ес- ли интерпретировать биты xt, …, xt+m–1 как двоичное представление номера i состояния конечного автомата, то граф этого автомата будет иметь 2m вершин, а следующее двоичное число xt+1, …, xt+m, совпадающее с номером следующего состояния автомата, будет равно: 2i, если xt = 0 и xt+m = 0; 2i + 1, если xt = 0 и xt+m = 1; 2i – 2m, если xt = 1 и xt+m = 0; 2i – 2m + 1, если xt = 1 и xt+m = 1. Полученные выражения полностью совпа- дают с указанными в условиях леммы 2. Лем- ма доказана. Маркировкой графа кодирующего автомата назовем способ, которым дугам графа сопос- тавляются символы, записываемые автоматом в код на выходе при соответствующих перехо- дах (способ сопоставления дугам графа битов входной последовательности несуществен, ес- ли считать, что значения каждого такого бита равновероятны). Хотя, как было показано, графы сверточных кодов имеют в определенном смыс- ле оптимальную структуру, нет оснований пола- гать, что маркировка графов сверточных кодов, даже самых эффективных, также оптимальна. Как отмечено ранее, в сверточном коде каждый из символов кодового слова может быть вычис- лен как результат линейной булевой функции, зависящей от номера состояния, в котором пре- бывает автомат, и считанного бита исходного сообщения. Представлять выходные символы как функции, зависящие от номера состояния кодирующего автомата и исходного бита, можно и в общем случае, рассматривая произвольные автоматы, однако эти функции не обязательно будут линейными. Логично предположить, что отказ от линейности может привести к повы- шению помехоустойчивости кода. Чтобы про- верить эту гипотезу, будем маркировать граф оптимальной структуры с помощью алгорит- ма 1, в котором недетерминированная состав- ляющая сочетается с некоторыми правилами маркировки. Алгоритм 1 маркировки графа генерирую- щего код автомата оптимальной структуры. 1. b ← 0. 2. Выбираем произвольно одну из четырех двухбитовых строк: 00, 01, 10 или 11 и марки- руем ею любую из дуг, выходящих из верши- ны b. Другую дугу, выходящую из b, маркиру- ем противоположной строкой (для 00 противо- положной будет строка 11, для 10 – 01 и на- оборот). 3. Пусть a – любая из двух вершин, таких, что существует дуга a → b, а c – вершина, в которую ведет другая дуга из вершины a. То- гда любой из двух дуг, выходящих из c, при- писываем одну из двух строк, не используе- мых при маркировке дуг, выходящих из b, а другую дугу, выходящую из c, маркируем про- тивоположной строкой. 4. Для всех вершин, из двух входящих дуг в которые маркирована только одна (строкой xy), маркируем другую входящую дугу строкой, противоположной к xy. 5. Присваиваем переменной b номер любой такой вершины, что входящие в нее дуги мар- кированы, а выходящие – нет, и переходим на шаг 2. Если таких вершин в графе нет, марки- ровка завершена. Корректность этого алгоритма, а также свойства конструируемой им маркировки ус- танавливает лемма 4. Лемма 4. Для любого кодирующего автома- та, граф которого удовлетворяет условиям леммы 2, алгоритм 1 корректен, а получаемая в результате его применения маркировка удов- летворяет следующим свойствам: 30 УСиМ, 2015, № 1  дуги, выходящие из одной вершины, мар- кируются противоположными строками: 00 и 11 либо 01 и 10, т.е. строками, расстояние Хэмминга между которыми составляет два;  дуги, входящие в одну вершину, марки- руются противоположными строками;  если существуют дуги a→b и a→c, то пе- реходы из вершин b и c маркируются разно- типными маркировками, т.е. если переходы из одной из этих вершин маркируются как 00 и 11, то переходы из другой вершины должны мар- кироваться как 01 и 10. Доказательство. Чтобы доказать коррект- ность работы алгоритма, следует установить два факта: во-первых, что после маркировки на шаге 4 не образуется вершин, одна из выходя- щих дуг из которых маркирована, а другая – нет; во-вторых, что перед шагом 5 не сущест- вует вершины, в которую входит одна марки- рованная дуга и одна немаркированная, либо из нее выходит одна маркированная дуга и од- на немаркированная. Из построения графа, описанного в лемме 2, следует, что в вершины с номерами 2i и 2i + 1 ведут дуги из вершин i и i + 2m–1. Это означает, что если существуют дуги a→b и a→c, то другие две дуги в верши- ны b и c также ведут из некоторой одной и той же вершины d (рис. 2,а). Заметим также, что если i = 0, то i = 2i и вершины a и b совпадают (рис. 2,б), а если i = 2m–1 – 1, то 2i + 1 = i + 2m–1 = = 2m – 1 и совпадают вершины c и d (рис. 2,в). Иначе говоря, на шагах 2 – 4 каждой итерации алгоритма выполняется маркировка всех дуг двух структур, подобных изображенным на одном из рис. 2а – в, и никаких других дуг, из чего и следуют два факта, позволяющие дока- зать корректность алгоритма, а также то, что каковы бы ни были вершины b и c, если существует неко- торая вершина e, из которой дуги ведут в b и c, то дуги, исходящие из b и c, маркиру- ются на одной итерации алго- ритма. Из последнего факта, а также из способа маркировки дуг на шаге 3 следует сфор- мулированное в условии леммы свойство 3. Свойство 1 из условия лем- мы следует непосредственно из способа мар- кировки дуг на шагах 2 и 3 алгоритма, а свой- ство 2 – из способа маркировки дуг на шаге 4. Лемма доказана. a=b= 0 c=1 d=2m–1 a= 2m–1–1 c=d=2m –1 b= 2m –2 b c a d а б в Рис. 2. Конструкции из четырех дуг в графе кодирующего автомата оптимальной структуры: а – 0 < a < 2m–1, б – a = 0, в – a = 2m–1 – 1 Выполнение указанных в условии леммы 4 свойств гарантирует, что расстояние Хэмминга между ветками любого двойного пути будет не меньше пяти, а также, что среднее расстояние Хэмминга между ветками всех двойных путей в графе кодирующего автомата будет достаточ- но большим. Последнее особенно существен- но, так как помехоустойчивость кода зависит не столько от величины dmin, сколько от упо- мянутого среднего расстояния. Применяя алгоритм 1 для генерирования мар- кировки графов кодирующих автоматов с 64 вершинами, т.е. с таким же количеством вершин, как и в графе сверточного кода памяти 6, напри- мер кода NASA (171,133), который наиболее эф- фективен из сверточных кодов памяти 6, полу- чено несколько кодов с более высокими поме- хоустойчивыми свойствами. Один из автоматов, Т а б л и ц а 2. Маркировка графа кодирующего автомата 0 00 11 8 01 10 16 01 10 24 00 11 32 11 00 40 10 01 48 10 01 56 11 00 1 10 01 9 00 11 17 11 00 25 01 10 33 01 10 41 11 00 49 00 11 57 10 01 2 01 10 10 01 10 18 01 10 26 00 11 34 10 01 42 10 01 50 10 01 58 11 00 3 11 00 11 00 11 19 00 11 27 01 10 35 00 11 43 11 00 51 11 00 59 10 01 4 00 11 12 00 11 20 01 10 28 01 10 36 11 00 44 11 00 52 10 01 60 10 01 5 01 10 13 10 01 21 00 11 29 00 11 37 10 01 45 01 10 53 11 00 61 11 00 6 00 11 14 01 10 22 01 10 30 00 11 38 11 00 46 10 01 54 10 01 62 11 00 7 01 10 15 00 11 23 00 11 31 01 10 39 10 01 47 11 00 55 11 00 63 10 01 УСиМ, 2015, № 1 31 генерирующих такой код, приведен в табл. 2. Первое число в каждой ячейке таблицы – это номер вершины. Записанная после него строка из двух двоичных символов – это мар- кировка дуги, ведущей из данной вершины i в вершину с четным номером, т.е. 2i или 2i – 2m, а вторая строка представляет собой маркиров- ку дуги, ведущей из вершины i в вершину с нечетным номером, т.е. 2i + 1 или 2i – 2m + 1. Сравнение эффективности данного кодиру- ющего автомата с эффективностью кода NASA (171,133) приведено в табл. 3, где показаны ре- зультаты декодирования по методу Витерби при использовании BPSK-модуляции и мягкого де- кодирования [4]. Как видно, при высоких соот- ношениях величины полезного сигнала и шума в канале связи (Eb\N0) вероятность ошибки на бит (BER) для предложенного кода ниже 3–8 про- центов, чем у кода NASA, а при боле низких зна- чениях величины Eb\N0 помехоустойчивость рассматриваемых кодов почти не отлича- ется. Т а б л и ц а 3. Сравнение эффективности сверточного кода и кода, сгенерированного конечным автоматом в соответствии с условием леммы 4 Eb/N0, дб BER, Сверточный код NASA(171,133) BER, Код, сгенерированный конечным автоматом –1 0,302 0,293 0 0,1551 0,1432 1 0,1309 0,1309 1,5 0,015 0,0145 2 0,005 0,0049 Отметим, что упомянутое преимущество дос- тигается не увеличением сложности кодирова- ния или декодирования по времени. Методы кодирования и декодирования для обоих кодов одинаковы за тем исключением, что в сверточ- ном коде значения битов строки-результата вы- числяются по формулам, а в предложенном ко- де извлекаются непосредственно из памяти, где хранится структура и маркировка кодирующе- го автомата. Второй способ даже быстрее, так как не предполагает выполнения сложений по модулю 2, хотя для его реализации требуется несколько больше памяти. Однако увеличение памяти, связанное с необходимостью хранения маркировок 64 вершин, для современных вы- числительных устройств несущественно. Заключение. Помехоустойчивая эффектив- ность сверточных кодов может быть повышена, если для генерирования символов кодовых слов вместо линейных функций использовать нели- нейные. При этом временная сложность кодиро- вания и декодирования не возрастает. Дальней- шее повышение помехоустойчивости может быть достигнуто благодаря применению различ- ных комбинаторных алгоритмов, определяющих позиции битов, значение которых было декоди- ровано с ошибкой. Поиск и исследование таких алгоритмов продолжается. 1. Shannon C.E. A mathematical theory of communication // Bell Syst. Techn. J. – July 1948. – 27. – P. 379–423; Shannon C.E. // Ibid. – Oct. 1948. – P. 623–656. 2. Analysis of low density codes and improved designs using irregular graphs / M. Luby, M. Mitzenmacher, A. Shokrollahi et al. // IEEE Trans. Inform. Theory. – 2001. – 47. – P. 585–598. 3. Berrou C., Glavieux A., Thitimajshima P. Near Shannon Limit Error-Correcting Coding and Decoding: Turbo- Codes // Proc. IEEE Int. Conf. Comm. (ICC93), Geneve, Switzerland, May 1993. – P. 1064–1070. 4. Morelos-Zaragoza R.H. The art of error-correcting coding. – John Wiley & Sons, 2002. – 220 p. Поступила 02.10.2014 E-mail: zava@ukr.net © И.А. Завадский, 2015 
id	nasplib_isofts_kiev_ua-123456789-87176
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0130-5395
language	Russian
last_indexed	2025-12-07T13:32:33Z
publishDate	2015
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
record_format	dspace
spelling	Завадский, И.А. 2015-10-14T08:05:30Z 2015-10-14T08:05:30Z 2015 Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов / И.А. Завадский // Управляющие системы и машины. — 2015. — № 1. — С. 25–31. — Бібліогр.: 4 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/87176 519.725 Предложен метод повышения эффективности сверточных помехоустойчивых кодов без увеличения вычислительных затрат на кодирование и декодирование. Сверточные коды рассматриваются как частный случай более общей схемы, где кодирование и декодирование выполняются конечным автоматом определенной структуры. Метод позволяет почти вдвое повысить уровень помехоустойчивости лучшего из известных сверточных кодов. The method of the convolutional codes empowering without increasing the computational complexity is presented. The convolutional code is considered as a partial case of more general schema where decoding and encoding are performed by a finite automaton of the certain structure. The proposed method outperforms the best convolutional code of the same graph size almost twice, having the same computational complexity. Запропоновано метод підвищення ефективності згорткових завадостійких кодів без збільшення обчислювальних витрат на кодування та декодування. Згорткові коди розглядаються як окремий випадок більш загальної схеми, де кодування та декодування виконуються скінченним автоматом певної структури. Метод дає змогу майже вдвічі покращити показники завадостійкості найкращого згорткового коду. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Проблемы информационного пространства и информационной безопасности Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов Improving the Efficiency of Error Correcting Convolutional Codes by Means of the Finite Automaton Article published earlier
spellingShingle	Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов Завадский, И.А. Проблемы информационного пространства и информационной безопасности
title	Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов
title_alt	Improving the Efficiency of Error Correcting Convolutional Codes by Means of the Finite Automaton
title_full	Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов
title_fullStr	Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов
title_full_unstemmed	Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов
title_short	Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов
title_sort	повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов
topic	Проблемы информационного пространства и информационной безопасности
topic_facet	Проблемы информационного пространства и информационной безопасности
url	https://nasplib.isofts.kiev.ua/handle/123456789/87176
work_keys_str_mv	AT zavadskiiia povyšenieéffektivnostisvertočnyhpomehoustoičivyhkodovspomoŝʹûkonečnyhavtomatov AT zavadskiiia improvingtheefficiencyoferrorcorrectingconvolutionalcodesbymeansofthefiniteautomaton

Повышение эффективности сверточных помехоустойчивых кодов с помощью конечных автоматов

Репозитарії

Схожі ресурси