Повышение эффективности методов кодирования для волоконно‑оптических линий связи

Теймуров Максим Теймурович магистрант, кафедра компьютерных систем, Новосибирский государственный университет 630090, Россия, Новосибирская область, г. Новосибирск, ул. Пирогова, 2 Teimurov Maksim Teimurovich Master degree student of the Department of Computer Systems at Novosibirsk State University 630090, Russia, Novosibirsk Region, Novosibirsk, str. Pirogova, 2 teymurov.maxim@gmail.com

Каждый год количество передаваемой между абонентами информации очень быстро увеличивается, поэтому остро стоит проблема улучшения средств передачи данных. По данным ежегодного прогноза Cisco к 2019 году всемирный трафик вырастет до двух зеттабайтов ^[1]. При этом основным средством передачи являются волоконно-оптические линии связи. В современном мире 70% всего и 99% межконтинентального трафика передается через них. Пропускная способность оптических линий все время растет и в настоящее время достигает порядка 20 Тбит/с. В лабораторных условиях удается продемонстрировать скорость передачи данных выше 100 Тбит/с.

Однако, при увеличении мощности передаваемых информационных импульсов в оптоволоконных линиях начинают играть большую роль так называемые нелинейные эффекты. Кроме физического они имеют еще и информационное влияние, которое проявляется в виде зависимости количества ошибок при передаче информации от вида самой информации — так называемым паттерн-эффектом (patterning effect) ^[2]. Примером паттерн-эффекта служит существование битовых последовательностей, которые передаются с ошибкой гораздо чаще, нежели остальные.

Особенно заметным паттерн-эффект становится при высоких скоростях передачи информации, так как на физическом уровне появляется межсимвольное взаимодействие (ISI — inter-symbol interference ^[3]) и ряд других физических эффектов такие как дисперсионное уширение импульса, четырёхволновое взаимодействие ^{[4, 5]} и фазовая кроссмодуляция ^[6]. Эти эффекты приводят к нелинейной зависимости информационных свойств канала от вида самой информации. Поэтому устранение негативных последствий нелинейных эффектов играет важную роль в развитии средств передачи данных.

Одним из способов решения этой проблемы — помехоустойчивое кодирование (FEC - Forward Error Correction), которое увеличивает избыточность сообщения, добавляя служебную информацию с помощью которой может быть восстановлено первоначальное сообщение. Многие методы хорошо справляются с исправлением небольшого количества ошибок для линий связи с невысоким BER (Bit Error Rate – количество ошибок в потоке данных по отношению к общему числу бит в потоке), но перестают работать или требуют высокой избыточности для линий связи с высоким BER > 0.1 и выше. Так же для многих методов при высокой избыточности растет сложность кодирования/декодирования, а с ней и стоимость оборудования.

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

Широко известными кодами с ограничениями являются RLL-коды (Run-Length Limited — коды с ограничением длины серий одинаковых битов). Данные коды описываются правилом наличия в слове между двумя «единицами» не менее , но не более «нулей». Эти коды можно разделить на две части: основанные на нумерации комбинаторных объектов и использующие специфические кодирующие конструкции. Первые обычно имеют высокую вычислительную сложность, а малый размер блока у вторых компенсируется большой избыточностью.

Для исследования паттерн-эффекта был использован программный комплекс для моделирования волоконно-оптических линий связи «OLSim-1» (Редюк А. А., Штырина О. В., Федорук М. П., Скидин А. С. Программный комплекс для моделирования волоконно-оптических линий связи «OLSim-1» // Свидетельство о государственной регистрации программы для ЭВМ № 2012613880 от 25.04.2012 г. (Федеральная служба по интеллектуальной собственности, патентам и товарным знакам)). С его помощью была проведена симуляция передачи случайной информации по многоканальной высокоскоростной линии связи с амплитудным методом модуляции сигнала на кластере информационно-вычислительного центра НГУ.

Моделируемая линия связи состоит из периодических секций, каждая из которых состоит из одного участка одномодового волоконного световода длиной 100 км, двух оптических усилителей (EDFA-1 и EDFA-2), отрезка волокна, компенсирующего дисперсию, а также блоков излучателя и приемника оптических сигналов. Для исследования использовались 80 таких секций, что соответствует передаче на 8000 км. По линии связи передается битовая последовательность длиной 32768 битов. На выходе получается битовая последовательность той же длины, но с ошибкой. Было проведено 100 таких экспериментов по моделированию.

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

На рис. 1 видно, что количество ошибок растет с длиной линии. Для того чтобы оценивать алгоритмы, мы выделим три точки на этом графике — 2500 км, 4500 км и 6500 км. При длине линии в 2500 км BER = 10^-4, на 4500 км BER = 4*10^-2 и на 6500 км BER = 1.3*10^-1, что позволит нам сравнить методы кодирования при небольшой, средней и большой вероятности ошибки.

Для исследования паттерн-эффекта мы будем рассчитывать вероятность ошибки в центре блока — битовой последовательности определенной длины. Соответственно для блоков длины строится таблица ошибок размером где строке соответствует вероятность ошибки в битовом представлении числа длиной бит.

Рис. 1: Зависимость BER от длины линии

Блок считается переданным ошибочно, если при передаче допущена ошибка в центральном бите. Например, если была передана последовательность 0110110, принята последовательность 0111110, а размер блока , то был ошибочно передан триплет 101.

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

В таблице 1 видно, что разные триплеты передаются с разной ошибкой, таким образом подтверждая, наличие в линии связи паттерн-эффекта. Так же видно, что минимальная и максимальная ошибка в блоке растет: для линии связи длиной 2500 км — 0 и 0,0062, для 4500 км — 0,0028 и 0,11, а для 6500 км — 0,03 и 0,26. Так же можно заметить, что лучше всего передается триплет 000, а хуже всего 101. Если выбрать последовательности, которые передаются с наибольшей ошибкой, то это будут 101, 11011, 1110111, 111101111, 11111011111 и 1111110111111.

Таблица 1: Вероятность ошибок для блоков длины три(триплетов)

В качестве блочного кода, который использует паттерн-эффект для уменьшения количества ошибок в линии связи, рассмотрим предложенный Скидиным А. С. метод адаптивного блочного кодирования(АБКС) ^{[2, 7, 8]}.

Рассмотрим код, который сопоставляет кодовые слова длины кодовым словам длины . Для построения кода построим вектор , который мы получим упорядочивая все возможные кодовые слова длины по убыванию вероятности их безошибочной передачи по волоконно-оптическому каналу. Далее вектор W будет использоваться для кодирования слов.

Представим кодовое слово в двоичном виде . Обозначим как i-е подслово длины . Тогда , и так далее. Всего подслов. Таким образом вероятность ошибки в кодовом слове a можно определить как:

где — вероятность появления ошибки в подслове . Тогда для вектора W , так как слова в векторе отсортированы по убыванию ошибок.

Для кодирования представим поток передаваемых данных S как последовательность небольших блоков длины () Обозначим через закодированное сообщение, где каждый блок имеет размер бит. Так как для кодирования используется только первые слов, можно хранить только их.

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

Его недостатком является большое потребление памяти с ростом размера блока. Для блока длины m требуется хранить две таблицы со всеми m-битными словами. Для длины блока равной 24 бита это требует памяти равной 2 · 24 · 224 бит, что составляет 96 мегабайт, а для длины в 32 бита - 2 · 32· 232 бита = 32 гигабайта.

Недостатком такого АБКС является то, что уменьшая количество подслов с высокой ошибкой внутри слова, он не учитывает подслова образующиеся на границе слов — т. н. краевой эффект. Для блока ошибки длины для анализа не будет использоваться бит, что для и составляет 12,5% длины слова, для и составляет 25% слова, а для и составляет уже 37,5% слова и так далее. Таким образом если учесть эту информацию, можно улучшить вышеприведенный АБК.

Возьмем для примера слово , где , , тогда вероятность ошибки в первом бите для второго бита , где . Можно сказать, что. Аналогично, для конца слова вероятность ошибки в последнем бите — , в предпоследнем . Если предположить, что нам известно это значение, то можно переопределить вероятность ошибки в кодовом слове:

где — вероятность появления ошибки в -м бите с начала слова . Аналогично, — вероятность появления ошибки в -м бите с конца слова .

Было предложено два метода вычисления и :

1. Метод «среднее»: разделяем подслово длины на две части — на неизвестную(в примере это ) и фиксированную (в примере это ). Тогда перебрав все значения , где для неизвестной части и взяв среднее мы получим вероятности и .

2. Метод «оптимальный»: так же разделяем подслово длины на две части — для перебора и фиксированную. Отличие от метода «среднее» - мы предполагаем, что некоторые подслова могут встречаться чаще других в начале или конце выбранного подмножества таблицы. Для нашего примера — последовательность встречается чаще в начале слов для подмножества расположенного в начале таблицы, отсортированной по частоте ошибок, чем . В таком случае нужно брать не среднее, а каждое значение умножать на вероятность того, что среди выбранных для кодирования слов в таблице () слово будет начинаться (заканчиваться) с , после чего суммировать.

Для «оптимального» метода возникает следующая проблема — нужно выбрать подмножество слов в таблице (), чтобы среди них считать вероятность того, что слово будет начинаться (заканчиваться) с . Количество всех подмножеств составит число сочетаний из по , что делает полный перебор всех таблиц для и невозможным. При этом в подмножестве с лучшим результатом с большей вероятностью там окажутся те слова, которые имеют меньшую вероятность ошибки, если оценивать их по формуле 1. Таким образом для выбора этого подмножества мы будем. сначала использовать для построения таблицы АБКС, а потом брать первые слов.

Для оценки АБКС на заданной ЛС была написана его реализация на языке С++. Мы будем рассматривать этот код с размером блока ошибок от 3 до 13 и избыточностью 4.3% до 100%.

На рис. 2 мы видим, что для АБКС с увеличением размера блока ошибок падает количество ошибок, что говорит о том, что учитываются паттерн-эффект для последовательностей большей длины. Однако, этот метод имеет недостаток – он не учитывает подслова, которые могут образовываться на границе кодовых слов.

Рис. 2: Коэффициент уменьшения ошибок для АБКС при длине линии связи 2500 км

Для анализа результатов АБКС при увеличении длины линии связи, построим график его работы для линий связи 2500 км, 4500 км, 6500 км с лучшим результатом относительно размера блока ошибки — 11, 13 и 13 бит соответственно. На рис. 3 показано, что АБКС достигает хороших результатов уже при небольшой избыточности в 4.3% устраняя от 20% — 60% в зависимости от длины линии связи.

Рис. 3: Коэффициент уменьшения ошибок для АБКС

Для оценки улучшения АБКС «среднее» на заданной ЛС была написана его реализация на языке С++. Мы будем рассматривать этот код с размером блока ошибок от 3 до 13 и избыточностью 4.3% до 100%.

Рис. 4: Коэффициент уменьшения ошибок для АБКС «среднее» при длине линии связи 2500 км

На рис. 4 мы видим, что для АБКС «среднее» с увеличением размера блока ошибок падает количество ошибок. При этом видно, что каждое следующее увеличение блока на два бита дает больший выигрыш, чем для «чистого» АБКС. Это можно объяснить описанной в п. 2.2 разницей в составлении таблицы ошибок — АБКС «среднее» учитывает образованные на границе слов другие подслова. Поэтому чем больше размер блока, тем больше разница между результатами. Например, для блока размером 3 с избыточностью в 5% разница между процентом исправленных ошибок у АБКС и у АБКС «среднее» - 0.04%. Зато для для блока размером 13 разница составляет уже 17%, что показывает преимущество АБКС «среднее» над «чистым» АБКС.

Аналогично АБКС, с ростом длины линии связи АБКС «среднее» исправляет все меньше ошибок. Для иллюстрации этого явления, мы выберем для длин линий связи 2500 км, 4500 км и 6500 км АБКС с тем размером блока ошибки, который показал самый лучший результат 11, 11 и 13 бит, соответственно. На рис.5 мы видим результат этого сравнения.

Рис. 5: Коэффициент уменьшения ошибок для АБКС «среднее» для линий связи разной длины

Преимущество улучшения «среднее» над «чистым» АБКС состоит в том, что оно позволяет использовать блоки ошибок большей длины, устраняя при этом большее количество ошибок.

Для оценки улучшения АБКС «оптимальное» на заданной ЛС была написана его реализация на языке С++. Мы будем рассматривать этот код с размером блока ошибок от 3 до 13 и избыточностью 4.3% до 100%.

Результаты почти совпадают с результатами АБКС «среднее», но лучше его примерно на 0.3% – 2.5%. Т. к. график АБКС «оптимальное» будет почти совпадать с графиком АБКС «среднее», то мы построим диаграмму разности этих улучшений.

На рис. 6 можно увидеть положительную разность, что указывает на то, что АБКС«оптимальное» исправляет больше ошибок, чем АБКС «среднее». При этом, графики имеют резкие переходы, так как предложенный способ для поиска вероятности того, что среди выбранных для кодирования слов в таблице слово будет начинаться (заканчиваться) с , не является оптимальным.

Рис. 6: Разница между результатами АБКС«оптимальное» и АБКС «среднее» для длины линии связи 2500 км

Результаты исследования показали, что адаптивное блочное кодирование способно исправлять ошибки для рассмотренной линии связи с высоким BER > 0.1 с небольшой избыточностью от 4.3%. Среди рассмотренных адаптивных блочных кодов лучшие результаты показал АБКС с «оптимальным» улучшением, потом с небольшим отставанием идет АБКС со «средним» улучшением, а последним идет «чистый» АБКС. Разницу между ними можно увидеть на рисунках 7, 8 и 9.

Недостатком АБКС является то, что при построении таблицы не анализируются подслова образующиеся на границе слов. При стремлении размера блока ошибок к размеру кодового слова, число не проанализированных бит стремится к 100% от размера слова. Предложенные улучшения решают эту проблему.

Рис. 7: Сравнение АБКС«оптимальное» и АБКС для длины линии связи 2500 км

Рис. 8: Сравнение АБКС «оптимальное» и АБКС для длины линии связи 4500 км

Рисунок 9: Сравнение АБКС «оптимальное» и АБКС для длины линии связи 6500 км

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

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