Метод помехоустойчивого кодирования телеметрической информации, исправляющий пропуски и инверсии битов Текст научной статьи по специальности «Компьютерные и информационные науки»

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Эльшафеи М. А.

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

Текст научной работы на тему «Метод помехоустойчивого кодирования телеметрической информации, исправляющий пропуски и инверсии битов»

Наука и Образование

МГТУ им. Н.Э. Баумана

Сетевое научное издание

Наука и Образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 10. С. 328-346.

Представлена в редакцию: 11.09.2014

Метод помехоустойчивого кодирования телеметрической информации, исправляющий пропуски и инверсии битов

:МГТУ им. Н.Э. Баумана, Москва, Россия

еЬЬа Геу ятаЦ. сот

Ключевые слова: корректирующие коды, сверточное кодирование, обработка телеметрической информации, пропуск инверсия битов

Для борьбы с шумами в канале связи с целью повышения надежности передачи телеметрической информации используются различные методы помехоустойчивого кодирования. Если характеристики канала связи известны и хорошо описываются моделью используемой кодером, помехоустойчивое кодирование может существенно снизить количество битовых ошибок при реконструкции информации на приемной стороне. Важным фактором в использовании кодера для помехоустойчивого кодирования является кодовая скорость, г=(^/п), где к - длина исходного сообщения, а п - длина кодированного передаваемого сообщения п = к + т, где т - добавленные проверочные биты.

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

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

В статье предложена расширенная модель канала связи, учитывающая эти три вида ошибок, и представлен метод повышения эффективности помехоустойчивого кодирования для случаев инверсии и пропуска битов. В работе проведен сравнительный экспериментальный анализ двух различных схем помехоустойчивого кодирования канала. Схема 1 включает один ЬБРС кодер со скоростью кодирования (к/2п). Схема 2 - это комбинированная схема кодирования канала, состоящая из ЬБРС кодера со скоростью кодирования (к/п) и блока свёрточного кодирования со скоростью кодирования (1/2). Такая схема позволяет исправлять ошибки вызванные выпадением битов из передаваемого по каналу потока данных. Схемы кодирования представлены на рис. 1.

Рис. 1. Схемы помехоустойчивого кодирования канала связи. (а) Схема 1 , (б) Схема 2 В работе описана общая модель канала связи с ошибками вызванными инверсией, выпадением и вставкой битов. Далее рассматривается частный случай этой модели, включающий обработку инверсии и выпадения битов.

Код с малой плотностью проверок на четность (ЬБРС) впервые был описан Робертом Г. Галлагером в 1961 г. [1,2] и впоследствии переработан в 90-х годах прошлого века [3,4]. Эффективность кода ЬБРС приближается границе Шеннона на расстояние 0,0045дБ [5].

Код ЬБРС это линейный блочный код, в котором для декодирования используется свойство ортогональности порождающей и транспонированной проверочной матриц:

Где С- порождающая матрица, Н - проверочная, и Т- транспонированная матрица. Проверочная матрица Н строится с помощью псевдослучайного генератора (полученные

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

где С - кодовое слово LDPC, длина которого равна (п) , X - кодируемые данные, длинной к, и С - порождающая матрица, размеры которой равны( к, п).

В случае если код систематический С, он описывается выражением

С = [1к | Рк *п - к] к *ш (3)

где Р - матрица чётности, I - единичная матрица.

Тогда, для каждого принятого без ошибок кодового слова, выполняется отношение:

а для принятого кодового слова содержащего ошибки:

Н=[ РТ I 1п - к ] п * п - к , (6)

где г — принятые данные, б — синдром.

Код LDPC представлен парой значений (п, к), где п - длина кодовых данных, а к -длина кодируемых данных. Проверочная матрица Н характеризуется малым количеством единичных битов. Если каждая строка матрицы Н содержит равное количество (/ <<

единиц (где ), и каждый столбец содержит равное количество

п) единиц, то код называют регулярным, а в противном случае - нерегулярным. Кодовая скорость кода LDPC определяется выражением ( Е = к/п). Формат кодового слова LDPC кодера представлен на рис 2.

Исходные данные биты проверки четности

Рис. 2. Структура кодового слова LDPC .

Проверочная матрица LDPC строится случайным или структурированным методом. Случайные коды LDPC обычно демонстрируют лучшие характеристики, (ближе к границе Шеннона), но имеют более сложную процедуру кодирования. К наиболее распространенным методам генерации случайной проверочной матрицы LDPC относятся метод Галлагера [2], и метод Маккея [4]. Структурированные LDPC коды имеют более низкую вычислительную сложность. К структурированным методам относятся: метод на основе суперпозиции [6], метод на основе матрицы Вендермонда [7], а также методы изложенные в [8, 9, 10, 11]. Квазициклический код QС — LDРС описан в [12,13,14] и коды, основанные на повторении основного кода (группа A RAJA ) [12,15,16], используются для

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

В целом при разработке алгоритмов кодирования LDPC основное внимание уделяется снижению сложности вычислений, и сохранению характера разреженности кода LDPC [12,17], а для декодирования имеется несколько итеративных алгоритмов, используемых, чтобы найти наиболее вероятные исходные данные из принятых закодированных данных, которые удовлетворяют условию формулы (4) [2].

Для декодирования используется алгоритм инверсии битов, выполняющий манипуляции с данными на битовом уровне [2,18] или один из алгоритмов описанных в [18,19,20].

2. Блок сверточного кодирования

Для обнаружения и исправления пропусков битов в потоке данных после передачи по каналу связи с шумами, модель которого допускает случайные инверсии и пропуски битов вводятся биты чётности [21,22,23,24]. В статье используется блок сверточного кодирования (модифицированная версия) для решения этой задачи [23,24] .

Свёрточные коды разработаны Элиасом в 1955 году [25]. Они имеют хорошую производительность, и простую стратегию декодирования. Сверточный код (п, к, г) определяется тремя параметрами; длина кодового слова (п) , длина сообщения (к ) и длина кодового ограничения (г). Сверточный код (п, к, г) включает в себя не только текущее сообщение, но и (г — 1 ) предыдущих сообщений. Параметр г = т — 1; где значение т -глубина памяти текущего кода. Коэффициент кодирования свёрточного кода определяется как отношение ( ) .

Для ( ) двоичного свёрточного кода, входное сообщение это двоичная последовательность ( ). Для каждого входного битового ( ) в момент времени , кодер производит разрядное бытовое кодовое слово по

Где ] = 1, 2 . п ; д/ £ < 0, 1 >- порождающий код.

На рис. 3 показана структура несистематического кодера двоичного свёрточного кода со свойствами;

с1 = гтФгт _ ! ©тс_ 2 ; с^ = тс ©тс _ 2 д 1 = ( 1 1 1 ) , д2 = ( 1 0 1 ) и коэффициент кодирования кода равен= 1 / 2 . й/гее это кодовое расстояние Хемминга йн между всеми возможными последовательностями кодовых слов.

й/ге е = т 1 п йн(С А, Св) = т / п йн ( С, 0 ) (8)

Где СА, Св , С - различные ненулевые кодовые последовательности.

Рис. 3. структура несистематического кодера двоичного свёрточного кода (2, 1 , 3 ).

Эффективность исправления любого свёрточного кода ^ определяется по формуле:

Где [. \ означает округление до ближайшего меньшего целого. Такая эффективность достигается, в случае, когда величины расстояния между ошибками больше или равны (V) .

Алгоритм Витерби, используемый для декодирования сверточных кодов, представлен в 1967 [26,27]. Он является оптимальным в смысле максимального правдоподобия [28] , и наиболее часто применяется на практике, поскольку имеет удовлетворительную эффективность и относительно низкую вычислительную сложность. Декодирование по алгоритму Витерби основано на поиске оптимального пути на решётчатой схеме. Этот оптимальный путь имеет наименьшую метрику ошибки (кодовое расстояние Хэмминга) между полученными и переданными данными.

Предложенный в [23,24] модифицированный алгоритм Витерби, который использует п декодеров для обеспечения коэффициента кодирования Е = к/п. Каждый декодер выполняет обработку данных сдвинутых на бит и вычисляет метрику ошибки для блока данных размером а битов. Значение а представляет собой количество битов, которые должны быть накоплены до того как очередной декодированный бит будет доступным на выходе декодера Витерби и определяет задержку декодирования. Обычно значение а выбирается равным 5 * V [12,23,24]. Для каждого декодера метрика накопленных ошибок на расстоянии а битов вычисляются по формуле ( 1 0 ). Далее выбирается выход декодера, который имеет минимальное значение метрики ошибки; т.е. т 1 п (А^) .

где - текущая метрика ошибки декодера , а - метрика ошибки декодера,

вычисленная на расстоянии а битов. Модифицированный алгоритм Витерби способен обнаруживать и исправлять (п — 1 ) выпадений битов в интервале а битов.

3. Перестановка битов

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

восстановления информации. Существуют разные способы перестановки [29-33]. В экспериментах использован подход, использующий случайную перестановку битов.

4. Модель канала связи с инверсией, пропуском и вставкой битов

Для описания канала связи предлагается следующая, основанная на результатах работ [21,22,23,24], общая модель канала связи с шумами, порождающими случайную инверсию, пропуск и вставку битов. Модель и диаграмма состояний показаны на рис. 4 и 5.

Рис. 4. Общая модель канала связи (а), симметричный двоичный канал (б), канал с вставкой битов (г), и

канал с пропуском битов (д).

Рис. 5. Диаграмма состояний общей модели канала связи.

5. Результаты экспериментов

Проведены два основных эксперимента, в каждом из которых использованы две описанные выше схемы помехоустойчивого кодирования: схема 1 и схема 2. Для ЬБРС декодирования данных применялся алгоритм инверсии битов.

В первом эксперименте для схемы №1 используется один кодер LDPC (2560,1024) Я = 0,4, построенный методом Галлагера, а для схемы №2 используется комбинация кодера LDPC (1280,1024) Я = 0, 8 , построенного методом Галлагера, и кодера сверточного кодирования на основе модифицированного алгоритма Витерби. Параметры этого кодера: (2,1, 3 ) с^ге е = 5 , g1 = 2 = 5.

На рис. 6 показаны результаты экспериментов с кодером ЬБРС с Я = 0, 4 , Я = 0, 5 и Я = 0, 8 для частного случая модели, учитывающего только случайную инверсию битов (рис.4 - б).

0.2 0.18 0.16 ё 0.14

2 0.1 § 0.08 £ 0.06 0.04 0.02 0

0.1 0.08 0.06 0,01 0,001

Вероятность ошибки бита (логарифмическая шкала)

Рис. 6. эффективность кодирования при передаче по каналу связи с учетом случайной инверсии битов.

На рис. 7 показаны результаты сравнения эффективности работы схемы №1 и схемы №2 в случае отсутствия пропусков битов ( так же согласно модели рис.4-б), для разных значений задержки о декодирования в схеме №2.

•. Кодер LDPC R=0.5 Кодер LDPC R=0.8 и свёрточное кодирование при ч =120 Кодер LDPC R=0.8 и свёрточное кодирование при ч =[10,20,40,60,80,100]

\ / \ ч = 40 \ Х ■ ж ч = 10

Вероятность ошибки бита (логарифмическая шкала)

Рис. 7. Сравнительный анализ эффективности кодирования схемы 1 и схемы 2 при отсутствии пропусков

битов, для разных значений о.

Результаты экспериментов показывают, что для частого случая модели, включающего только возможность инверсии битов, выбор LDPC кодера предпочтителен для вероятностей битовых ошибок Ре > 0.065, при том, что для меньших значений вероятности ошибки эффективность обеих схем примерно одинакова. Для Ре < 0.05 на длинных блоках схема 2 демонстрирует лучшую эффективность.

На рис. 8 показаны результаты экспериментов со схемой 2 для отличных от нуля вероятностей пропуска и инверсии битов. Этот случай соответствует моделям, представленным на рис 4-б и 4-д. Эксперименты проводились для разных значений вероятности инверсии битов , а также для разных значений для схемы 2.

Вероятность ошибки бита (логарифмическая ш

Рис. 8. Эффективность схемы 2 по каналу связи для моделей (4-б и 4-д) при разных значениях а

(а) Ра = . 0 0 1 , (б) Ра = . 003, (г) Ра = .005 и (д) Ра = . 0 0 1 Значения задержки декодирования а показаны в следующей таблице

Таблица 1. Выбранные значения задержки декодирования а

\ Ре 0 0,001 0,0025 0,005 0,0075 0,01 0,025 0,05 0,055 0,06 0.1

0.001 20 60 60 60 60 100 120

0.002 20 40 40 120

0.003 20 40 40 80 80

0.009 10 10 10 20 40

0.05 10 10 10 10

Из таблицы 1 следует, что в случае передачи данных по каналу связи с вероятностью пропуска бита Ра Ф 0 , величина задержки декодирования а должна быть низкой. Это значение увеличивается с ростом вероятности ошибки инверсии бита .

Проведены сравнительные анализы эффективности декодирования с помощью схем 1 и 2 при передаче данных по каналу связи, который описывается моделью (4-б и 4-д). В этом эксперименте использованы значения а , полученные ранее в экспериментах рис.8.

вероятность выподения бита (логарифмическая шкала)

вероятность ошибки бита (логарифмическая шкала)

вероятность выподения бита (логарифмическая шкала)

вероятность ошибки бита (логарифмическая шкала)

Рис. 9. Эффективность декодирования (а) схемы 1 и (б) схемы 2 при передаче по каналу связи

описываемому моделью (4-б и 4-д)

Заметим, что при канале связи модели (б) (без выпадения битов Ра = 0 ), эффективность схемы№2 равна (а даже лучше) эффективности схемы№1 до Ре = 0,065 , но при модели (б и д) эффективность схемы№2 лучше, чем эффективность схемы№1, а также скорости кодирования схемы№ 1 и схемы№2 равны, Я = 0 ,4 .

Во втором эксперименте использованы коды LDPC (2 560, 1024) й = 2 / 5 и LDPC (1408, 1024) й = 8/ 1 1 (группа Лй 4/Л) , описанные в [12,15,16]. Для целей эксперимента были построены порождающие и проверочные матрицы таких кодов по описанию [12]. Следует отметить, что скорость кодирования в схеме 2 й = 4 / 1 1. Основные полученные результаты показаны на рис. 10 , 11.

Рис. 10. Эффективность кодирования для модели 4-б.

—•—Кодер LDPC К=2/5 —•—Кодер LDPC К=4/7 Кодер LDPC К=8/11 и свёрточное кодирование при ч =120

📎📎📎📎📎📎📎📎📎📎

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Эльшафеи М. А.

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Эльшафеи М. А.

Текст научной работы на тему «Метод помехоустойчивого кодирования телеметрической информации, исправляющий пропуски и инверсии битов»