Анализ исправления ошибок типа «Стирание» П-кодом в каналах передачи данных

ТРУДЫ БГТУ. 2013. № 6. Физико-математические науки и информатика. С. 123-126

123

УДК 681.325.3

Ю. О. Булова, ассистент

АНАЛИЗ ИСПРАВЛЕНИЯ ОШИБОК ТИПА «СТИРАНИЕ» П-КОДОМ В КАНАЛАХ ПЕРЕДАЧИ ДАННЫХ

Статья посвящена проблеме повышения качества передаваемой информации в каналах с ошибками типа «стирание». Рассмотрены алгоритмы кодирования и декодирования нового П-кода, основанного на фонтанном LT-коде с использованием W-циклического перемежителя. Разработано программное средство, с помощью которого произведен сравнительный анализ исправляющей способности LT- и П-кодов. Проанализирована возможность применения данных кодов в современных системах связи.

The article is devoted to the quality improvement of the transmitted information in channels with errors such as "erase". Algorithms of encoding and decoding of the new P-code based on the fountain LT-code using the W-cycle interleaver. Developed a software tool that allows comparative analysis of the ability of the guide used LT-and P-codes. The using possibility of codes in modern communication systems is analyzed.

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

Основными методами, направленными на повышение надежности передаваемой информации в таких каналах связи, являются:

- использование обратного канала от получателя к отправителю;

- помехоустойчивое кодирование информации с использованием случайных фонтанных кодов [1].

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

Основная часть. Для разработки нового фонтанного кода необходимо учитывать основные требования, предъявляемые к данному классу кодов [2]:

- код должен представлять собой потенциально неограниченный поток символов;

- кодер должен генерировать «на лету» новые кодовые символы, значения которых не зависят от предыдущих;

- алгоритм декодирования должен быть быстрым.

В качестве основы для создания нового П-кода использовались ЬТ-код [3] и 'Ациклический перемежитель [4].

Алгоритм кодирования можно разбить на нескольких этапов.

1. Первый этап кодирования заключается в формировании кодовых символов со степенью й = 2 (количество исходных символов для ге-

нерации кодового символа). Кодирование на данном этапе происходит, пока выполняется условие (1):

0 < i < K - 1,

где г - номер исходного символа, вовлеченного в операцию кодирования, К - размер исходного сообщения.

Из сообщения последовательно выбираются по 2 исходных символа sг с шагом к = 2 и суммируются по модулю 2, образуя новый кодовый символ X] (2):

х = S

i + h

Каждый следующий кодовый символ включает в себя исходные символы, следующие за предыдущими, вовлеченными в операцию кодирования, через 1 бит (рис. 1).

Исходное сообщение

1 0 1 0 1 1 0 1 1 0 1 1

Xi

ы

Кодовые символы

И

Рис. 1. Схематическое представление первого этапа кодирования

2. Кодирование на втором этапе происходит согласно формуле 2, однако начинается со смещения, т. е. операция кодирования происходит, пока выполняется условие 3 (рис. 2).

1 < i < K -1.

s

S

Исходное сообщение

1 0 1 0 1 1 0 1 1 0 [ 1

И ш

Кодовые символы

Рис. 2. Схематическое представление второго этапа кодирования

3. Третий этап кодирования заключается в формировании кодовых символов со степенью 3 путем последовательного суммирования трех соседних символов исходного сообщения по модулю 2 (4).

X = 5

7 '

>5 Ф 5 .

1 + к/2 1 + к

Кодирование продолжается, пока выполняется условие 1 (рис. 3).

Исходное сообщение

1 0 1 0 1 1 0 1 1 0 1 1

И

и и

Кодовые символы

Рис. 3. Схематическое представление третьего этапа кодирования

4. Четвертый этап кодирования аналогичен третьему, но происходит согласно условию 2 (рис. 4).

Исходное сообщение

1 0 1 0 ] 1 0 1 1 0 1 1

н

Кодовые символы

Рис. 4. Схематическое представление четвертого этапа кодирования

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

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

При кодировании образуется бинарная матрица, номер строки которой соответствует индексу кодового символа, а позиции единиц в строке - номерам исходных бит, входящих в данный кодовый символ. Кодовое слово соответствует первому столбцу матрицы (рис. 5).

К

Ь

0 1 0 1 0 0 0 0

1 0 0 0 0 1 0 1

0 0 1 0 1 0 0 0

0 0 0 0 0 0 1 0

0 1 1 1 0 0 0 0

1 0 0 0 0 1 1 1

1 0 1 1 1 0 0 0

0 0 0 0 0 0 1 1

Рис. 5. Бинарная матрица кодирования

Сформированные кодовые символы образуют кодовые пакеты из Ь бит.

Группирование ошибок затрудняет обеспечение высокой эффективности с использованием только лишь средств кодирования. Поэтому для декорреляции ошибок типа «стирание» предлагается использовать Ж-циклический перемежитель:

п(7) = 7 • Ж mod Ь,

где п( 7) - местоположение разряда 7 после пе-ремежения; Ж - шаг перемежения - некоторое целое число, взаимно простое с Ь, причем

[0,382 • Ь_|-2 < Ж <[0,382 • Ь\ + 2.

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

Для деперемежения используется следующая формула:

п'(7) = п(7) • Ь mod Ь,

где п'( 7) - местоположение разряда п( 7) после деперемежения; Ь - шаг деперемежения:

Ь =

т • Ь+1 Ж :

5

X

X

X

Анализ исправления ошибок типа «стирание» П-кодом в каналах передачи данных

125

где т - целое число 0 < т < Ь — 1, при котором значение Ь - целое число.

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

1. Определяется степень кодового символа.

2. Если степень кодового символа ^ = 1 -устанавливается 57 = х, тем самым находится 7-й символ (рис. 6).

Бинарная матрица

0 1 0 1 0 0 0 0

1 0 0 0 0 1 0 1

0 0 1 0 1 0 0 0

0 0 0 0 0 0 1 0

0 1 1 1 0 0 0 0

1 0 0 0 0 1 1 1

1 0 1 1 1 0 0 0

0 0 0 0 0 0 1 1

Декодированное сообщение

0

Рис. 6. Процесс декодирования

Удаляются копии 7-го символа (9):

х = х ф 5 .

] } 7

Из всех списков номеров кодовых символов удаляется номер /: строка бинарной матрицы суммируется по модулю 2 с бинарной строкой, содержащей единицу в позиции/, что приводит к понижению степеней соответствующих кодовых символов (рис. 7).

Бинарная матрица

0 1 0 1 0 0 0 0

1 0 0 0 0 1 0 1

0 0 1 0 1 0 0 0

0 0 0 0 0 0 0 0

0 1 1 1 0 0 0 0

1 0 0 0 0 1 0 1

1 0 1 1 1 0 0 0

0 0 0 0 0 0 0 1

Рис. 7. Процесс декодирования

3. Если степень кодового символа ^ Ф 1 -строка бинарной матрицы, соответствующая анализируемому кодовому символу X/, поочередно суммируется по модулю 2 с бинарными строками всех кодовых символов, в формировании которых участвовал первый исходный символ из X/. Таким образом, получаются новые кодовые символы, и процесс декодирования переходит к шагу 1 (рис. 8).

Бинарная матрица

0 1 0 1 0 0 0 0 ...

0 0 0 0 0 0 0 0

0 0 1 0 1 0 0 0

0 0 0 0 0 0 0 0

0 1 1 1 0 0 0 0 . ♦ ♦

0 0 0 0 0 0 0 0

1 0 1 1 1 0 0 0

0 0 0 0 0 0 0 0

Нов ое к дов ое с ово

0 0 1 0 0 0 0 0

Рис. 8. Процесс декодирования

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

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

Для анализа эффективности ЬТ- и П-кода строится диаграмма, на которой отображается избыточность указанных выше кодов на каждом испытании (рис. 9).

Проанализирована избыточность для различных размеров (К) исходного сообщения и размеров (Ь) кодовых пакетов в каналах с заданным количеством одиночных и группирующихся ошибок типа «стирание».

Произведенный анализ показал, что ЬТ-код позволяет декодировать полученное сообщение в канале без произошедших ошибок типа «стирание» с избыточностью 10-50%, в то время как П-код способен декодировать сообщение с избыточностью, близкой к нулю.

При появлении небольшого количества стираний в канале связи более эффективным

Рис. 9. Скриншот программного средства с графиком избыточности ЬТ- и П-кодов при N = 100 бит, Ь = 10 бит

является П-код (при наличии в канале 5% стираний П-код способен декодировать сообщение при избыточности в среднем 20%), однако с увеличением количества стираний (20% и более) его эффективность значительно снижается.

Необходимо отметить, что новый П-код также позволяет пропустить стадию начальной синхронизации между кодером и декодером, которая занимает в зависимости от параметров канала связи 2-60 с.

Заключение. Рассмотрены алгоритмы кодирования и декодирования нового П-кода. Произведен сравнительный анализ исправляющей способности ЬТ- и П-кода.

Таким образом, П-код может использоваться в каналах как с обратной, так и без обратной связи; позволяет пропустить стадию начальной синхронизации между кодером и декодером; показывает лучшую эффективность в сравнении с ЬТ-кодом в каналах с небольшим количеством ошибок типа «стирание» (до 20%).

Однако следует учитывать, что описанные коды не способны обнаружить ошибку в ситуации, когда переданное кодовое слово было пре-

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

Литература

1. Варгаузин, В. Помехоустойчивое кодирование в пакетных сетях / В. Варгаузин // ТелеМультиМедиа. - 2005. - № 3. - С. 10-16.

2. Булова, Ю. О. Кодовые методы нейтрализации ошибок типа «стирание» в каналах передачи двоичной информации / Ю. О. Булова // Труды БГТУ. - 2012. - № 6: Физ.-мат. науки и информатика. - С. 142-145.

3. Luby, M. LT codes / M. Luby // Proc. 43rd Ann. IEEE Symp. on Foundations of Computer Science. - 16-19 November 2002. - C. 271-282.

4. Gorbunova, Yu. W-ciclic method interleaving of data for communication system / Yu. Gorbunova, P. Urbanovich // News electrical and electronic technologies and their industrial implementation: procc. VII International Conference, Zakopane, Poland, June 28 - July 1, 2011. - P. 149.

Поступила 22.03.2013