Владимиров С.С. и соавт. Постобработка при декодировании последовательностей …
ПОСЛЕДОВАТЕЛЬНОСТЕЙ МАЛОГО СЕМЕЙСТВА
КАСАМИ НА ОСНОВЕ ДВОЙСТВЕННОГО БАЗИСА
ПОСТОБРАБОТКА ПРИ ДЕКОДИРОВАНИИ
С.С. Владимиров1*, О.С. Когновицкий1
1Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч-Бруевича,
Санкт-Петербург, 193232, Российская Федерация
*Адрес для переписки: vladimirov.opds@gmail.com
Информация о статье
УДК 621.391
Язык статьи – русский
Ссылка для цитирования: Владимиров С.С., Когновицкий О.С. Постобработка при декодировании последовательностей
малого семейства Касами на основе двойственного базиса // Труды учебных заведений
связи. 2018. Т. 4. № 4. С. 5–12. DOI:10.31854/1813-324X-2018-4-4-5-12
Аннотация: В современных системах цифровой передачи для синхронизации передаваемых данных широко
используются псевдослучайные последовательности различного вида, например, М-последовательности и
последовательности Касами. Предлагается использовать эти последовательности одновременно для
синхронизации и адресации абонентов, применяя специальные методы декодирования. В статье рассматривается
метод декодирования последовательностей малого семейства Касами на основе двойственного
базиса с использованием постобработки принимаемых кодовых комбинаций.
Ключевые слова: последовательности Касами, малое множество последовательностей Касами, двойственный
базис, вероятность ошибки.
Введение
В современных цифровых системах передачи
данных, как правило, передаются в виде отдельных
блоков – кадров. Для выделения кадров используют
два способа передачи: синхронный и
асинхронный. В первом случае имеется отдельный
источник синхросигнала, обеспечивающий синхронную
передачу и прием данных. Во втором случае
в начале каждого кадра присутствует специальная
кодовая последовательность, преамбула,
которая позволяет выделить кадр в общем зашумленном
потоке сигналов, передаваемом по каналу.
Часто в качестве синхропоследовательностей используют
псевдослучайные последовательности
различного вида, такие как, например, последовательности
максимальной длины (М-последовательности)
или производные из них составные
последовательности Голда, ЛРД-последовательности
и последовательности Касами [1–4].
Следует отметить, что М-последовательности и
последовательности, образованные из них, фактически
представляют собой кодовые комбинации
соответствующих помехоустойчивых кодов с большой
избыточностью. Например, помехоустойчивый
код, состоящий из всех возможных М-последовательностей
над одним конечным полем Галуа,
получил название кода максимальной длины [5].
DOI:10.31854/1813-324X-2018-4-4-5-12
5
Аналогично можно сформировать помехоустойчивые
коды и из составных последовательностей.
Информационной частью кодового слова в таком
случае будут служить начальные фазы М-последовательностей,
образующих кодовое слово.
Таким образом, помимо задач синхронизации,
приведенные псевдослучайные последовательности
можно использовать как традиционные помехоустойчивые
коды для передачи данных, а также
комбинировать задачи синхронизации и передачи
данных. Например, ранее авторами был предложен
метод одновременной синхронизации и адресации
посредством кодовых комбинаций кода
максимальной длины [6, 7]. Адресами при этом
являются начальные фазы М-последовательностей,
соответствующих кодовым комбинациям кода.
При использовании кода над полем Галуа степени
n, за исключением нулевой кодовой комбинации,
в этом методе можно адресовать до (2n − 1)
абонентов.
Использование кодов на основе составных последовательностей
позволяет увеличить долю полезной
информации при сохранении общей длины
кодовой комбинации. Для примера рассмотрим
последовательности малого семейства Касами.
tuzs.sut.ru
Стр.1
ТРУДЫ УЧЕБНЫХ ЗАВЕДЕНИЙ СВЯЗИ
Последовательность малого семейства Касами
{s} формируется над полем GF(2n), где степень n
должна быть четным числом. Сама последовательность
Касами {s} является составной с периодом
N1 = 2n – 1 и представляет собой поэлементную
сумму М1-последовательности максимального периода
{u}, порождаемой примитивным многочленом
h1(x) степени n, и М2-последовательности {v},
порождаемой неприводимым многочленом h2(x)
степени n/2 [8, 9]. Таким образом, в одной последовательности
Касами переносится два блока полезной
информации: начальная фаза c М1-последовательности
{u} и начальная фаза d М2-последовательности
{v}. Следовательно, в одной последовательности
может быть передан либо один блок полезных
данных длиной (c + d), либо каждая из
начальных фаз может переносить отдельную полезную
информацию.
Для декодирования последовательностей Касами
могут использоваться различные алгоритмы
[10–14]. В частности, может быть использован метод
мажоритарного декодирования на основе
двойственного базиса [4, 15]. В статье рассмотрена
методика постобработки последовательности Касами,
позволяющая увеличить исправляющую способность
данного алгоритма.
Постобработка последовательности малого
семейства Касами при декодировании
на основе двойственного базиса
Как было показано в статье [15], при мажоритарном
декодировании последовательности {s}
малого семейства Касами с использованием двойственного
базиса, т.е. при определении начальных
фаз c и d, составляющих ее М-последовательност
{u} и {v} соответственно, возможны три результата
декодирования:
1) правильное декодирование, когда вычисленные
начальные фазы совпадают с реальными;
2) неправильное декодирование, когда вычисленные
начальные фазы не совпадают с реальными
(это случай необнаруженной ошибки);
3) отказ от декодирования, когда декодер не
может однозначно определить значение начальной
фазы хотя бы одной из М-последовательностей
(это случай обнаруженной ошибки).
В случае отказа от декодирования часть таких
результатов составляют те, в которых по принципу
максимального правдоподобия выделяется несколько
значений начальной фазы с одинаковым
наибольшим весом. Одно из этих значений может
являться правильным. При этом можно провести
постобработку такой последовательности, которая
в ряде случаев позволит однозначно определить
правильное значение начальных фаз.
Постобработка основана на том, что в случае нескольких
вариантов начальной фазы c М1-последовательности
{u}, мы можем на основе каждого из
DOI:10.31854/1813-324X-2018-4-4-5-12
6
2018. Т. 4. № 4
вариантов ci начальной фазы сформировать соответствующую
ему М1-последовательность {ui}, а затем
сложить ее с принятой последовательностью
Касами {s}, получив в результате набор М2-последовательностей
{vi} с точностью до вектора ошибки.
Далее по принципу максимального правдоподобия
можно исправить ошибки в М2-последовательности
{vi}. Если при использовании одной из начальных
фаз ci последовательность {vi} определяется однозначно,
то такая начальная фаза считается правильной
фазой М1-последовательности {u}, а начальная
фаза определенной последовательности
{vi} считается правильной начальной фазой М2-последовательности
{v}.
С другой стороны, в случае отказа, который возник
по причине получения нескольких вариантов
начальной фазы d М2-последовательности {v} при
однозначном выделении начальной фазы c М1-последовательности
{u} можно предположить, что начальная
фаза c получена правильно, и рассмотренным
в предыдущем абзаце способом попытаться
вычислить начальную фазу d.
Рассмотрим принцип этой постобработки на
примере нескольких вариантов начальной фазы c
М1-последовательности {u}.
Для формирования последовательности Касами
{s} = {s0, s1, ..., s62} выберем М1-последовательность
{u} = {u0, u1, ..., u62} над полем степени n1 = 6 с образующим
полиномом g1(x) = x6 + x + 1, имеющую
начальную фазу c = 1910 = ε16, и соответствующую
ей М2-последовательность {v} = {v0, v1, ..., v6} над
полем степени n2 = 3 с образующим полиномом
g2(x) = x3 + x2 + 1, начальная фаза: d = 310 = μ5. В результате
будет получена составная последовательность
{s} малого семейства Касами, представленная
в таблице 1.
Предположим, что в результате передачи по каналу
связи на последовательность {s} был наложен
вектор ошибки {e}, как показано в таблице 2. В результате
была получена последовательность
{se} = ({s} + {e})[mod 2].
При декодировании последовательности {se} по
методу двойственного базиса были получены два
варианта значения начальной фазы c и одно значение
начальной фазы d:
c1 = 1910 = ε16; c2 = 4510 = ε44; d = 310 = μ5.
Вначале возьмем первое значение начальной фазы
c1. Вычислим по нему последовательность {u1} и
сложим с принятой последовательностью {se}, как
показано в таблице 3, получив повторенную 9 раз
предполагаемую последовательность {v1} с точностью
до вектора ошибок {e}.
Далее по методу максимального правдоподобия
попытаемся исключить вектор ошибок {e} из предполагаемой
последовательности {v1}. С этой целью
сравниваем значения в каждом из разрядов девятикратно
повторенной предполагаемой последоtuzs.sut.ru
Стр.2
Владимиров С.С. и соавт. Постобработка при декодировании последовательностей …
вательности {v1} как показано в таблице 4. В том
случае, если 1 повторяется не менее 6 раз, т.е. отношение
числа единиц к числу нулей в позиции не
меньше 6/3, то считаем, что в этой позиции значение
1. Если это отношение равно 3/6 или меньше,
то считаем, что в этой позиции значение 0. При
отношениях 5/4 и 4/5 считаем, что в этой позиции
однозначно указать значение невозможно – на нее
приходится слишком много ошибок.
Таким образом, при заданных соотношениях
числа единиц и нулей была получена последовательность
{v1}, которая предположительно не содержит
ошибок. Далее проводим проверку того,
действительно ли полученная последовательность
является последовательностью максимальной
длины, чтобы исключить ситуации, когда число
ошибок в позиции больше пяти. Декодирование
данной М-последовательности, например, методом
двойственного базиса [4, 16, 17], позволяет
определить значение начальной фазы: d1 = 310 = μ5.
При работе в канале, в котором может возникать
заведомо большое число ошибок, имеет
смысл ужесточить требования к отношению числа
единиц к числу нулей. К примеру, для данной последовательности
можно фиксировать 1 при соотношении
не хуже 7/2, а 0 при соотношении 2/7 и
менее. Прочие соотношения считать ошибками, и
в случае получения только одной такой ошибки
проводить декодирование М-последовательности,
которое позволит эту ошибку исправить.
Аналогично по второму значению начальной
По методу максимального правдоподобия пытаемся
исключить вектор ошибок {e} из предполагаемой
последовательности {v2} (таблица 6). Позиции,
значение которых не определяется однозначно,
отмечены символом «x».
Как видно из таблицы 6, однозначно определить
последовательность {v2} не представляется
возможным.
Таким образом, при проверке двух возможных
канала АБГШ
Модель
реВывод
зультата
Сравнение
начальных
фаз
( Декодер
ый базис)
Блок постобработки
торой
несколько значений начальной фазы ci позволяют
определить М2-последовательность {v},
следует считать заведомо ошибочной и рассматривать
как обнаруженную ошибку (отказ от декодирования).
DOI:10.31854/1813-324X-2018-4-4-5-12
7
б)
Рис.
1. Модели системы передачи для проверки алгоритма
декодирования с постобработкой при использовании моделей:
а) канала ДСК; б) канала АБГШ при модуляции ФМ-2
ндвойственДемодулятор
ФМ-2
значений
начальной фазы c М1-последовательности
{u} было определено, что только одно из них,
значение c1, позволяет определить М2-последовательность
{v}. Следовательно, именно это значение
и является верным, что подтверждается сравнением
с исходно выбранными для вычисления
последовательности Касами значениями начальных
фаз.
Также следует отметить, что ситуацию, при кон
Генератор
ачальных
фаз
реВывод
фазы c2 вычисляем последовательность {u2} и определяем
повторенную 9 раз предполагаемую последовательность
{v2} с точностью до вектора
ошибок {e} (таблица 5).
Вероятностные характеристики декодера
последовательности Касами на основе
двойственного базиса с постобработкой
при синхронном декодировании
Для статистической проверки работоспособности
алгоритма декодирования с постобработкой и
для получения вероятностных характеристик, демонстрирующих
исправляющую способность алгоритма,
было проведено моделирование по методу
Монте-Карло с использованием свободной системы
математических вычислений GNU/Octave. Моделирование
произведено для случая синхронной
передачи данных, при котором кодовая последовательность
вначале полностью выделяется приемником,
а затем уже производится ее декодирование
(рисунок 1).
В качестве моделей канала связи выбраны классическая
модель двоичного симметричного канала
(ДСК), которая показана на рисунке 1а и модель канала
с абсолютно белым гауссовским шумом (АБГШ)
при модуляции ФМ-2 (рисунок 1б). Использованы
стандартные программные реализации выбранных
моделей каналов из пакета расширений COMMUNICATIONS,
входящего в систему GNU/Octave. При моделировании
производился одновременный набор
статистики для простого декодирования по методу
двойственного базиса и для декодирования с постобработкой,
что позволило сравнить их на одинаковом
наборе переданных данных.
н Генератор
ачальных
фаз
зультата
Сравнение
начальных
фаз
Генератор
Касами
к Модель
( Декодер
ый базис)
Блок постобработки
а)
Генератор
Касами
Модулятор
ФМ-2
ндвойственанала
ДСК
tuzs.sut.ru
Стр.3