Что такое скорость кода

5. — Скорость кода (коэффициент кода)

Граничные соотношения между характеристиками помехоустойчивого кода. I. Граница Хемминга.Сколько в этой зоне запрещенных + 1 кодовых комбинаций? Разделим на и прологарифмируем: Граница Хемминга(граница плотной упаковки сферы) Коды на границе Хемминга и есть сами коды Хемминга. II. Граница Варшамова – ГилбертаРазделим на и прологарефмируем: упрощенное выражение для границы Варшавова — Гилберта Таких кодов значительно больше, чем кодов, удовлетворяющих границы Хемминга, и эти коды хорошие. III. Граница максимально разнесенных кодов (максимальная граница)Устанавливает максимальное значение для определенной избыточности. Таких кодов мало: коды с проверкой на четность и другие. Ее открыл Синглтон (граница Синглтона). Классификация помехоустойчивых кодов.Групповые коды. Определение группы и её свойства. Блоковые коды – характеризуются длиной кодовой комбинации n (n-последовательность). Действия над кодовыми комбинациями – поразрядное сложение (по mod2)/ Группа – одна из основных систем, рассматриваемых в высшей математике. Группой (G) называется множество элементов произвольной природы, для которых задано одно из действий (либо сложение, либо умножение). И по этому действию (операции) это множество обладает следующими свойствами (удовлетворяют следующим аксиомам):

1. Замкнутость.

Рассмотрим на примере сложения (для умножения тоже самое).

1. Ассоциативность (сочетательность).

1. Наличие единичного элемента.

Среди элементов группы есть единственный элемент l, такой что для любого элемента группы a выполняется соотношение: Например,

1. Наличие обратных элементов.

Для каждого элемента a группы в группе есть обратный элемент такой что

1. Коммутативность.

Если a и b элементы группы и не важен порядок, т.е. то такая группа называется коммутативной или абелевой. Группа называется конечной, если она состоит из конечного числа элементов. В противном случае она называется бесконечной. Пример. Задав в качестве групповой операции операцию сложения по mod2, убедимся, что множество 000, 001, 010, 100, 110, 011, 101, 111 является группой. Складывая элементы множества в различном сочетании, видим, что каждый раз получаем элемент, входящий в множество. Так, и т.п. Легко заметить, что условие ассоциативности также выполняется. Единичным является элемент 000. Для каждого элемента, заданного в примере множества, существует обратный. Так, для элемента 100 обратным является он сам, т.е.. Таким образом, рассматриваемое множество является группой, порядок которой (число элементов) равен восьми. Видно также, что данная группа является коммутативной. Групповым кодом называется множество n-последовательностей, которые являются абелевой группой по введённой операции поразрядного сложения . Для групповых кодов принято обозначение (n,k) – код (k – число информационных элементов, n – общее число элементов). Свойства групповых кодов.

1. Групповой (линейный) код является подгруппой множества всех последовательностей длины n. (А множество всех последовательностей длины n называется группой).

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

1. Min кодовое расстояние группового кода равно весу его ненулевых комбинаций.

Это свойство обусловлено тем, что сумма любых комбинаций группового кода также является кодовой комбинацией, а значит комбинация min веса указывает на степень удалённости комбинаций данного кода. Любой групповой код не обнаруживает только те ошибки, которые по своему виду совпадают с видом кодовой комбинации. Способы задания групповых кодов. a₀, a₁, a₂, a₃, … a_n-1 – последовательность длины n. — вектор n-мерного пространства (— скаляр,— орт). N_П ~ V_П N_К ~ V_К

1. Базис – совокупность линейно независимых векторов, с помощью которых можно получить все вектора, входящие в это пространство.
2. Линейная комбинация кодовой комбинации.

1. Линейная зависимость и линейная независимость. (Линейная независимость: W = 0, когда все с_i= 0)

Способы задания.

1. По аналогии с линейным векторным пространством можно задавать групповые коды с помощью базиса подпространства размерности k n-мерного векторного пространства. [Порождающая матрица кода (ПМК)]

Строками этой таблицы являются k линейно независимых кодовых комбинаций. ПМК обозначается: (), , []. Пример. Пусть в групповом (5,3) коде связи между информационными и избыточными элементами задаются с помощью следующих линейных отношений: Элементы комбинаций кода a₀, a₁, a₂, a₃, a₄, где a₂, a₃, a₄ — информационные, а a₀, a₁ – избыточные элементы. Избыточные элементы могут быть получены путём суммирования по mod2 определённых информационных элементов. Т.о. ,. 00 000 10 100 11 010 01 110 01 001 11 101 10 011 00 111 Первые два столбца – это избыточные элементы, полученные путём суммирования по mod2 определённых информационных элементов, а оставшиеся три столбца – информационные элементы. Исходя из этого можно построить ПМК: R I ПМК – служит для краткого задания кода. Для однозначности задания кода с помощью порождающей матрицы вводится понятие канонической формы порождающей матрицы: n

1. Проверочная матрица группового кода (Н).

Свойство. Если два вектора по скалярному произведению равны нулю, то они ортогональны. Смотри предыдущий пример. a₀, a₁, a₂, a₃, a₄Проверочные вектора R` — базис нулевого пространства (5,3) кода. H – базис нулевого пространства (n,k) кода. в качестве строк – проверочные вектора данного кода. n-k n-k k , k–транспонированная проверочная матрица. Проверочная матрица группового кода как и ПМК может быть записана в канонической форме: Т.о. проверочная матрица как и ПМК служит для краткого задания кода. Она задаёт код через проверочные соотношения, существующие для данного кода. Используя связь между канонической формой ПМК и проверочной матрицей мы легко по одной из них находим другую.

11.09.2019 1.41 Mб 1 Конспект по ЖБК.doc

15.03.2015 1.64 Mб 32 Конспект-Лекций Электромагнетизм.pdf

15.03.2015 294.76 Кб 35 Контр_ПИС_Заоч.docx

15.03.2015 547.2 Кб 45 Контроллер GATE-4000_ред5.pdf

17.09.2019 594.94 Кб 1 КОНТРОЛЬНЫЕ ВОПРОСЫ К ЗАЧЕТУ.doc

15.03.2015 1.33 Mб 39 Копия ПДС.doc

29.03.2016 198.14 Кб 75 КОСМИЧЕСКИЕ И НАЗЕМНЫЕ СИСТЕМЫ РАДИОСВЯЗИ И ТЕЛЕРАДИОВЕЩАНИЯ.doc

15.03.2015 716.7 Кб 67 Коспект лекций по ФОЭ.pdf

15.03.2015 749.92 Кб 8 КП.pdf

29.03.2016 45.03 Кб 4 КР ВЕКТ&АНАЛИТ 15 00.docx

23.12.2018 88.06 Кб 3 КР2 дто.doc

Ограничение

Для продолжения скачивания необходимо пройти капчу:

Кодовая скорость

В телекоммуникационной и информационной теории , то скорость коды (или скорость передачи информации [1] ) о наличии прямой коррекции ошибок коды является долей потока данных , который полезен (без резервирования). То есть, если кодовая скорость соответствует каждому биту полезной информации, кодер генерирует все биты данных, из которых избыточны. k / п k п п — k

Если это полная скорость передачи битов или скорость передачи сигналов данных (включая избыточное кодирование ошибок), то чистая скорость передачи данных (полезная скорость передачи данных без учета кодов исправления ошибок) равна . р ≤ р ⋅ k / п

Например: Скорость кода из сверточного кода обычно будет , , , , и т.д., соответствующий одному избыточный бит , вставленного после каждого одного, второго, третьего и т.д., немного. Кодовая скорость октетов ориентированных Рида — Соломон блочного кода обозначается RS (204,188) является 188/204, а это означает , что избыточные октеты (или байты) добавляются к каждому блоку 188 октетов полезной информации. 1 / 2 2 / 3 3 / 4 5 / 6 7 / 8 204 — 188 знак равно 16

Некоторые коды с исправлением ошибок не имеют фиксированной кодовой скорости — бесскоростные коды стирания .

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

См. Также [ править ]

• Скорость передачи информации
• Скорость исходной информации (скорость энтропии)
• Прокалывание

Ссылки [ править ]

1. ^ Хаффман, В. Кэри, и Плесс, Вера, Основы кодов с исправлением ошибок , Кембридж, 2003.

скорость передачи кода

Для произвольного блочного кода или сверточного кода с параметрами (n,r) эта величина определяется как R=r/n. Она является мерой эффективности кода в том смысле, что чем больше избыточность кода, тем меньше скорость его передачи. Вместе с тем высокая избыточность может обеспечить в такой же степени большую эффективность исправления или обнаружения ошибок. Таким образом, скорость передачи кода отражает только один аспект его общей эффективности.

English-Russian dictionary of information security . 2014 .

• сквозное шифрование в сети
• скрытый канал временной

Смотреть что такое «скорость передачи кода» в других словарях:

• скорость равномерного кода — Отношение логарифма объема кода к его длине. Примечание Скорость линейного кода равна умноженному на логарифм числа символов в алфавите источника отношению числа символов в информационном слове к длине кода. [Сборник рекомендуемых терминов.… … Справочник технического переводчика
• скорость древовидного кода — Величина, представляющая собой отношение числа символов в отрезке сообщения к числу сопоставляемых им кодовых символов в блоке n, умноженное на логарифм числа символов в алфавите источника; она равна . [Сборник рекомендуемых терминов. Выпуск 94.… … Справочник технического переводчика
• Скорость передачи информации — Разъём 8P8C. Скорость передачи информации скорость передачи данных, выраженная в количес … Википедия
• скорость — 05.01.18 скорость (обработки) [rate]: Число радиочастотных меток, обрабатываемых за единицу времени, включая модулированный и постоянный сигнал. Примечание Предполагается возможность обработки как движущегося, так и неподвижного множества… … Словарь-справочник терминов нормативно-технической документации
• ГОСТ Р 51385-99: Элементы процедур передачи и форматы служебных пакетов (сообщений) в широкополосной цифровой сети интегрального обслуживания с быстрой коммутацией пакетов. Требования к процедурам и форматам — Терминология ГОСТ Р 51385 99: Элементы процедур передачи и форматы служебных пакетов (сообщений) в широкополосной цифровой сети интегрального обслуживания с быстрой коммутацией пакетов. Требования к процедурам и форматам оригинал документа: 2.2… … Словарь-справочник терминов нормативно-технической документации
• ОСТ 45.163-2001: Спутниковые линейные тракты передачи сигналов цифрового телевидения. Основные параметры. Методы измерений — Терминология ОСТ 45.163 2001: Спутниковые линейные тракты передачи сигналов цифрового телевидения. Основные параметры. Методы измерений: Глубина перемежения число пакетов транспортного потока на выходе внешнего колера, на которое распространяется … Словарь-справочник терминов нормативно-технической документации
• модифицированная версия кода MR — Схема кодирования факсимильных изображений, которая позволяет существенно снизить объем передаваемых данных и обеспечить более высокую скорость передачи страницы текста за счет исключения кода EOL и других упрощений изображения. Применяется в… … Справочник технического переводчика
• Многоборье МР-3 — Логотип радиомногоборья. Многоборье радистов (радиомногоборье, МР 3) дисциплина радиоспорта. Номер код спортивной дисциплины во Всероссийском реестре видов спорта 1450021811Я. Включает три вида программы: перед … Википедия
• ГОСТ 22670-77: Сеть связи цифровая интегральная. Термины и определения — Терминология ГОСТ 22670 77: Сеть связи цифровая интегральная. Термины и определения оригинал документа: 10. n ичный сигнал электросвязи n агу digital signal Цифровой сигнал электросвязи, имеющий п возможных состояний представляющего параметра,… … Словарь-справочник терминов нормативно-технической документации
• ГОСТ Р ИСО/МЭК 19762-1-2011: Информационные технологии. Технологии автоматической идентификации и сбора данных (АИСД). Гармонизированный словарь. Часть 1. Общие термины в области АИСД — Терминология ГОСТ Р ИСО/МЭК 19762 1 2011: Информационные технологии. Технологии автоматической идентификации и сбора данных (АИСД). Гармонизированный словарь. Часть 1. Общие термины в области АИСД оригинал документа: Accredited Standards… … Словарь-справочник терминов нормативно-технической документации
• КОД С ИСПРАВЛЕНИЕМ ОШИБОК — код, корректирующий ошибки, множество сообщений, предназначенных для передачи по каналу связи с шумами, обладающее тем свойством, что окрестность ошибок каждого сообщения (т. е. совокупность искаженных вариантов этого сообщения) не пересекается с … Математическая энциклопедия

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

СВЕРТОЧНЫЕ КОДЫ / ПЛЕТЕНЫЕ КОДЫ / МПП-КОДЫ / КОДЫ ПРОВЕРКИ НА ЧЕТНОСТЬ / КОДИРОВАНИЕ / ИТЕРАТИВНОЕ ДЕКОДИРОВАНИЕ / СВОБОДНОЕ РАССТОЯНИЕ / АКТИВНОЕ СТРОЧНОЕ РАССТОЯНИЕ / CONVOLUTIONAL CODES / LDPC CODES / ENCODING / ITERATIVE HARD DECISION DECODING / FREE DISTANCE / ACTIVE ROW DISTANCE

Аннотация научной статьи по математике, автор научной работы — Кондрашов Константин Александрович, Зяблов Виктор Васильевич

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Кондрашов Константин Александрович, Зяблов Виктор Васильевич

Мягкое декодирование произведений кодов произвольной размерности на базе кодов с единственной проверкой четности

Алгоритм декодирования с вводом стираний для МПП -кодов, построенных над полем GF(q)
Помехоустойчивые коды цифрового телевидения
Параллельное каскадное вероятностное декодирование кодов низкой плотности проверок на четность
Пороговое декодирование недвоичных самоортогональных сверточных кодов
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Two Binary Woven Convolutional Code Constructions

In this contribution, a new construction of binary low-density parity-check (LDPC) woven convolutional codes is discussed. In this construction, component codes with single parity check are used. The latest allows woven code rate adaptation without changing corresponding encoder and decoder and decreases computational complexity. An iterative hard decision decoding algorithm and its modification with erasures insertion is introduced. Code properties and decoding performances are studied.

Текст научной работы на тему «Конструкция плетеных сверточных кодов на базе кодов проверки на четность с одним проверочным символом»

X кодирование и передача информации

конструкция плетеных сверточных кодов на базе кодов проверки на четность с одним проверочным символом

младший научный сотрудник В. В. Зяблов,

доктор техн. наук, профессор

Институт проблем передачи информации им. А. А. Харкевича РАН

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

Ключевые слова — сверточные коды, плетеные коды, МПП-коды, коды проверки на четность, кодирование, итеративное декодирование, свободное расстояние, активное строчное расстояние.

Блочные коды с малой плотностью проверок на четность (МПП-коды) и итеративный алгоритм их декодирования были предложены Р. Гал-лагером еще в начале 1960-х [1]. Структура этих кодов потенциально позволяет получать малые вероятности ошибок для кодов с высокой скоростью при низкой сложности декодирования. Коды Галлагера являются каскадными кодами, в которых в качестве кодов-компонентов используются коды проверки на четность с одним проверочным символом. Такие коды-компоненты являются кодами с максимально достижимым кодовым расстоянием (МДР), легкодеко-дируемы и существуют на всех длинах, что позволяет получать МПП-коды с произвольными скоростями.

В данной статье мы рассматриваем сверточные варианты МПП-кодов. Мы предлагаем конструкцию сверточных МПП-кодов [2], в которой в качестве кодов-компонентов также используются коды проверки на четность с одним проверочным символом. Последнее позволяет естественным образом, не изменяя кодер и декодер, варьировать скорость получаемых кодов. Для ко-

дов разработанной конструкции мы также предлагаем два итеративных алгоритма декодирования с жестким принятием решений [3, 4]. Для сравнения корректирующих свойств кодов мы рассматриваем похожую конструкцию сверточных МПП-кодов с меньшим числом кодов-компонентов, разработанную К. Зигангировым, Д. Трухачевым и М. Лентмайером [5]. Рассматриваемые сверточные МПП-коды мы называем плетеными сверточными кодами (П-СМПП-кодами).

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

Пусть и = иои1 . и . и = [и1^,2 — Щ,ъ\’ V = ^ . vt — V = [Ч,1Ч,2~Ч, ] Щ, Р Щ, i 6 ¥2 ответственно информационная и проверочная последовательности сверточного кода со скоростью R = Ъ/с, Ъ < с. Пусть

— транспонированная полубесконечная проверочная матрица этого кода, называемая также формирователем синдрома. Подматрицы HT(t), i = 0, 1, . ms — двоичные матрицы размера c х (c — b). Величина ms называется памятью формирователя синдрома. Мы требуем, чтобы выполнялись следующие два условия:

rank HT(t) = c — b, t e N;

Hm (t) ^ 0, t e N, t > ms.

Любая кодовая последовательность v удовлетворяет уравнению vHT = 0 или, в рекуррентной форме:

vtH0 (t) + vt-1Hl (t) + + vt-ms Hms (t) = 0, t e N- (2)

Если строки h„ матрицы HT разрежены, т. е. ro_ff(hn) ^ (c — b)ms, где ия(-) — вес Хэмминга, то сверточный код является МПП-кодом.

Для любого МПП-кода (для сверточного — с момента времени t = ms) если в каждом столбце проверочной матрицы ровно J единиц, а в каждой строке ровно K единиц, то МПП-код называется регулярным (далее мы рассматриваем только регулярные МПП-коды). Такой код можно рассматривать как состоящий из J внутренних кодов-компонентов проверки на четность длины K. Каждая строка проверочной матрицы в таком случае трактуется как код проверки на четность, образованный из символов кодового слова с номерами позиций, на которых в этой строке стоит 1.

Конструкции плетеных сверточных мПП-кодов

В работе Галлагера, посвященной блочным МПП-кодам [1], было показано, что МПП-коды с кодами-компонентами с одной проверкой на четность с минимальным расстоянием di = 2 обладают хорошими корректирующими свойствами (кодовое расстояние растет линейно с длиной кода) в том случае, если используется J ^ 3 кодов-компонентов. И хотя мы строим сверточные МПП-коды, мы все же придерживаемся этого требования. Мы предлагаем конструкцию 4-плетеного сверточного МПП-кода (4-П-СМПП) с J = 4 кодами-компонентами [2].

Опишем конструкцию 4-П-СМПП-кода. В 4-П-СМПП-коде каждый символ кодового слова входит в 4 кода-компонента — в «горизонтальный», «вертикальный» и два «диагональных» кода-компонента, а само кодовое слово образуется из «переплетения» кодов-компонентов. Представим кодовое слово 4-П-СМПП-кода в виде полубесконечного массива двоичных символов (рис. 1, а). В строках такого массива хранятся кодовые слова горизонтального кода-компонента, в столбцах — кодовые слова вертикального кода-компонента, а по диагоналям располагаются кодовые слова диагональных кодов-компонентов. На рисунке изображено кодовое слово 4-П-СМПП-кода с длиной кодов-компонентов 8. Индексами обозначены символы, образующие кодовые слова четырех кодов-компонентов в произвольный момент времени t. На момент времени t серые ячейки представляют известные, закодированные ранее символы. На вход подается информационный блок ut, ut = [ut 1ut 2ut 3ut 4]. Выходом vt служит кодовое слово горизонтального кода-компонента. Память формирователя синдрома представленного кода ms = 7, скорость R = 1/2, кодовое ограничение (ms + 1) c = 64, а компонентные проверочные матрицы формирователя синдрома соответственно равны

[1 0 0 1′ [0 0 0 0′ [0 0 0 0′ [0 0 0 0′ [0 1 0 0′ [0 0 0 0′ [0 1 0 0′ [0 0 0 0′

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

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

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

1 0 0 0 , 0 0 0 0 , 0 1 0 0 , 0 0 0 0 , 0 0 0 1 , 0 0 0 0 , 0 0 1 0 , 0 0 0 0

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

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

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

н 0 н1 н 2 н 3 н4 н5 н 6 н7

Кодирование 4-П-СМПП-кода осуществляется следующим образом. В произвольный момент времени t параллельно кодируются вертикальный и диагональные коды-компоненты — все их информационные символы уже известны. Затем кодируется горизонтальный код-компонент — полученные от остальных кодов-компонентов проверочные символы вместе с символами кодируемого информационного блока и4 образуют его информационные символы. Кодовое слово горизонтального кода-компонента формирует выход.

Если из конструкции 4-П-СМПП-кода исключить два диагональных кода-компонента, то получившийся 2-П-СМПП-код будет описываться уже известной конструкцией [5]. В работах [5, 6] в качестве кодов-компонентов 2-П-СМПП-кода рассматривались коды с минимальным расстоянием di ^ 3. В этом случае было доказано, что свободное кодовое расстояние 2-П-СМПП-кода растет линейно с длиной кодового ограничения (т8 + 1)с. Тем не менее, в рамках поставленной задачи в качестве кодов-компонентов 2-П-СМПП-кода, как и в случае 4-П-СМПП-кода, мы будем использовать коды проверки на четность с ^ = 2.

Опишем конструкцию 2-П-СМПП-кода со скоростью Я = 1/2. Представим кодовое слово 2-П-СМПП-кода с кодами-компонентами длины 4 в виде полубесконечного массива двоичных символов (рис. 1, б). Конструктивно этот массив разбивается на три «полосы» (на рисунке отделены жирной линией). В нижней полосе хранятся проверочные символы кодовых слов вертикального кода-компонента, в центральной полосе хранятся информационные символы кодируемой последовательности, в верхней полосе — проверочные символы кодовых слов горизонтального кода-компонента. Кодовое слово

горизонтального кода-компонента V1 образуется из символов

vt, 1 vt, 2 и, 1 vt

«(2) «(2) и «(2) vt, 1 vt, 2 и, 2 vt

образуют кодовое слово v(t2) вертикального кода-компонента. Информационный блок состоит из символов и = [щ щ 2]. В любой момент времени і проверочный символ горизонтального кода-компонента V(t1) вычисляется с помощью символов информационной последовательности и и закодированного ранее проверочного символа вертикального кода-компонента vt2^ Проверочный символ вертикального кода-компонента вычисляется по аналогии с использованием изве стных символов и и V(t1). Закодированный в момент времени і блок V = \рі V 2уі 3оі 4] состоит из следующих символов:

І 2 • «І-2, 3 £ і £ 4

Память формирователя синдрома представленного кода т8 = 3, кодовое ограничение (т8 + 1) х х с = 16, а компонентные проверочные матрицы формирователя синдрома соответственно равны

1 1′ 0 0 0 0 0 0

1 0 0 1 0 0 0 0

1 0 , 0 0 , 0 1 , 0 0

1 0 0 0 0 0 0 1

Построение ансамбля плетеных сверточных кодов

Для построения ансамбля сверточных плетеных МПП-кодов мы воспользуемся методикой, предложенной в работе [7]. МПП-коды можно представить в виде графа Таннера [8] — двудольного графа, где один набор вершин соответствует символам МПП-кода (символьные вершины), а второй — проверкам кодов-компонентов МПП-кода (проверочные вершины). Выполняя различные преобразования над исходным графом МПП-кода, можно получить новые МПП-коды. Так, для построения ансамбля П-СМПП-кодов £(Е) мы будем использовать выбираемые равновероятно случайные матрицы перестановок P размера L х L. Применим к исходному графу B операцию «копирование с перестановками» [7]: Ь;, j = Ь;, р;, . Каждому ребру графа B ставится в соответствие матрица перестановки, все узлы графа копируются L раз, а конечные точки ребер переставляются. В качестве примера на рис. 2 показано преобразование с коэффициентом L = 3 графа

110 0 0 111 1110

Преобразование увеличивает в L раз длину кода N, с, Ь и кодовое ограничение.

АВС АВС АВС 2301230123

АВС АВС АВС ■ Рис. 2. Копирование протографа с перестановками

Кодирование плетеных сверточных кодов

Кодировать П-СМПП-коды можно несколькими способами. Первый из них уже был описан при построении конструкций. Однако он не является оптимальным [9]. С аналогичной сложностью, но с меньшим требованием к памяти можно кодировать П-СМПП-коды с помощью частичных синдромов.

Опишем алгоритм кодирования. В любой момент времени г кодовая последовательность v удовлетворяет условию

[0, і-1]Н[0, t+ms-í] = [[0, і-1]

где si = [в* ^ 2..^ т] — вектор частичных синдромов. На самом деле, вектор частичных синдромов si — это не что иное, как состояние аі кодера сверточного кода в момент времени і. Вектор частичных синдромов вычисляется рекуррентно в соответствии со следующим правилом:

8і-1,і+1 + уі-1н° (і + І-1Ь і = !>■■■>т8-1 Уі-1Ні (і + т8 -ІЬ І = т8

Пусть, без потери общности, символы информационного блока ^ стоят на первых Ь позициях кодового блока vі. Пусть \і — [уі | у і], уі — иі. Напомним, что подматрица ^^і), і є N имеет полный ранг с — Ь. Тогда кодовый блок уі — [уі | находится из решения

Необходимый для кодирования таким способом объем памяти составляет (с — Ь)т8 бит. Сложность кодирования линейна относительно длины N П-С-МПП-кода.

При аппаратной реализации кодирования для вычисления частичных синдромов можно использовать сдвиговый регистр (рис. 3). В этом

уг—1Нт3 (t + + т8 -1)

Мультипликатор частичных синдромов

■ Рис. 3. Схема сверточного кодера на основе частичных синдромов

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

Оценка кодового расстояния

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

Определение 1. Минимальное расстояние между любыми различными кодовыми последовательностями сверточного кода называется свободным расстоянием:

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

Определение 2. Активным строчным расстоянием dj сверточного кода называется минимальный вес терминированного кодового слова v^, j], не проводящего кодер через два последовательных нулевых состояния:

dj = min: v[h j]Hf1; j+ms —1 = 0.

Свободное расстояние связано с активными расстояниями следующим отношением:

Для нахождения активных расстояний dj мы будем решать для различных длин j систему линейных уравнений

из которой исключены первые несколько строк, отвечающие нулевым проверочным символам вертикального и диагональных кодов-компонентов в первом кодовом блоке. Система (7) имеет или единственное нулевое решение, или множество решений. В последнем случае найденные линейно независимые решения системы (7) образуют фундаментальную систему решений (ФСР), линейная оболочка которой дает все решения системы (7). Найдем среди векторов линейной оболочки ФСР ненулевой вектор с минимальным весом. Его вес даст точное значение активного расстояния dj. Однако таким способом можно рассчитать лишь ограниченное число начальных активных расстояний. Сложность перебора векторов линейной оболочки растет экспоненциально с числом найденных решений, поэтому, по мере увеличения /, которое также увеличивает размерность ФСР, мы быстро сталкиваемся с вычислительным ограничением. Результаты моделирования по вычислению активных расстояний рассмотренных П-СМПП-кодов представлены на рис. 4. Большее число кодов-компонентов и возросшая память повлияли на увеличение активных и свободных расстояний 4-П-СМПП-кодов по сравнению с 2-П-СМПП-кодами. Расширение 4-П-СМПП-кодов при L > 1 также увеличивает активные расстояния. Однако при расширении 2-П-СМПП-кода расстояния не изменились (на рис. 4 активные расстояния 2-П-СМПП-кодов с L = 1 и L = 4 совпадают). Отметим, что на графиках для некоторого ./тах, ] < ]тах для каждого кода наблюдаются значения dj = да. Это означает, что при данных значениях / система (7) не имеет никаких решений, кроме тривиального. Следовательно, для рассматриваемых П-СМПП-кодов не существует пакетов ошибок с длиной до /тах.

2-П-СМПП, L = 1 -©- 2-П-СМПП, L = A -а- 4-П-СМПП, L = 1 — 4-П-СМПП,Ь = 2

■ Рис. 4. Активные расстояния П-СМПП-кодов

Декодирование плетеных сверточных кодов

Для представленных П-СМПП-кодов мы предлагаем два итеративных алгоритма декодирования с жестким принятием решения [3, 4]: мажоритарный алгоритм Л1 и его расширенный вариант Л2 с введением стираний.

Для начала опишем обобщенную процедуру декодирования, которую можно применять к П-СМПП-кодам с произвольными кодами-компонентами. Введем необходимые обозначения. Пусть г — принятое из канала слово, содержащее ошибки. На произвольной итерации i, i е N на вход декодера подается слово г©, где г(1) = г, выходом декодера является слово г(; + 1). Для декодирования слов, относящихся к определенным кодам-компонентам, используются соот-

«——л;ие компонентные декодеры

> , если компонентные декодеры спо-

собны исправлять как ошибки, так и стирания.

Каждая итерация декодирования обобщенным алгоритмом состоит из двух частей: внутреннего декодирования — декодирования слов кодов-компонентов и внешнего декодирования — принятия решения по каждому символу слова П-СМПП-кода. При внутреннем декодировании слов кодов-компонентов никакие символы декодируемого слова не заменяются, вместо этого значения символов, полученные от внутренних декодеров, запоминаются в памяти. В результате внутреннего декодирования для каждого символа слова г© в памяти хранится J решений — по решению от J декодеров кодов-компонентов. При внешнем декодировании для каждого символа слова г© на основании этих J значений принимается решение об изменении. Результатом становится слово г(; + 1).

Обобщенный алгоритм декодирования

Внутреннее декодирование. Для каждого кода-компонента & с помощью декодера компонента D(k) декодируются все соответствующие ему слова из г©. Результаты запоминаются в г&®.

Внешнее декодирование. Для каждого символа г/;) входного слова г© значение г() вместе со

полученными для этого

символа при внутреннем декодировании, подается на вход функции голосования. Эта мажоритарная функция возвращает г& + 1) со значением, которое встречалось среди ее входных аргументов чаще других. Из всех г( + 1) формируется слово следующей итерации г(; + 1).

Критерии останова. Логическим критерием завершения декодирования является нулевое значение синдрома, полученного после некоторой ите-

рации i слова г(* + 1). Однако изменение синдрома с каждой итерацией может носить произвольный характер. Поэтому для гарантии останова алгоритма мы вводим ограничение на число итераций. Таким образом, возможны следующие результаты декодирования: успех декодирования; ошибка декодирования; отказ от декодирования.

Успех декодирования. Успех декодирования происходит в том случае, если синдром выходного слова г(; + 1) нулевой и декодированное кодовое слово совпадает с переданным: 5(г(; + 1)) = 0, г(; + 1) = ^

Ошибка декодирования. Происходит при нулевом синдроме, когда принятое слово декодировалось в другое кодовое слово, не совпадающее с переданным: 5(гС + 1)) = 0, г(; + 1) ф ^

Отказ от декодирования. Отказ происходит при ненулевом синдроме, если достигнут предел итераций или результирующее слово итерации г@ + 1) не отличается от входного слова итерации г(;): 5(гС + 1)) ф 0, г@ + 1) = г© V i = 1тах.

Алгоритм декодирования П-СМПП-кодов с кодами-компонентами с одним проверочным символом Л1 получается из обобщенного алгоритма декодирования выбором подходящих декодеров для внутреннего декодирования. Сами по себе коды с одним проверочным символом способны лишь обнаруживать ошибки, но не исправлять их. Поэтому внутреннее декодирование несколько отличается от того, что обычно под этим понимается. В алгоритме Л1 при внутреннем декодировании для каждого слова кода-компонента & декодер D(k) изменяет каждый символ слова так, чтобы с учетом этого изменения декодируемое слово удовлетворяло проверке на четность.

Для двоичных П-СМПП-кодов с четным числом кодов-компонентов во время процедуры голосова-

ния возможна ситуация, когда продекодированные

символа г(і) делятся поровну.

В этом случае логично подозревать символ г() на ошибку, но алгоритм Л1 не приводит к его изменению. На поздних итерациях, когда большинство ошибок исправлено (или внесены новые устойчивые ошибки), невозможность изменить спорный символ приводит с большой вероятностью к отказу декодирования, так как декодируемое слово не изменяется. Чтобы иметь возможность продолжить декодирование, мы предлагаем ассоциировать с символом новую качественную характеристику и считать такой «ненадежный» символ стертым.

Определение 3. Стирание — качественная характеристика символа, означающая, что его значение не определено. При отсутствии ошибок код с минимальным расстоянием d способен исправить до d — 1 стираний.

Алгоритм Л2 также построен на основе обобщенного алгоритма декодирования, но он работа-

ет с учетом стираний. В алгоритме декодирования Л2 при голосовании спорные символы объявляются стертыми. На внутреннем декодировании

используются компонентные декодеры

исправляющие стирания. Если декодируемое слово кода-компонента & не содержит стираний, то Е(к) работает как D(k). Если слово содержит одно стирание, то значение стертого символа заменяется с учетом выполнения проверки на четность и стирание снимается. Если стираний в слове больше одного, то слово не изменяется. При внешнем декодировании значения стертых символов в голосовании не участвуют, а решение для символа принимается, если число совпавших продекодированных значений этого символа больше половины числа кодов-компонентов. При исправлении стираний новые

стирания не образуются, а значит, стирания либо будут полностью декодированы, либо будет получена неисправимая комбинация стираний. В последнем случае мы снимаем с оставшихся символов значение стирания: продолжается декодирование с исправлением ошибок. Критерии останова и возможные значения на выходе алгоритма Л2 аналогичны критериям и значениям алгоритма Л^

Декодирование итеративным алгоритмом

Моделирование проводилось для 2-П-СМПП-кода длины 2400 бит с кодами-компонентами (4,3)-кодами проверки на четность и 4-П-СМПП-кода длины 2400 с кодами-компонентами (8,7)-кодами проверки на четность. Выходные вероятности ошибки на бит (Bit-Error-Rate — BER) и ве-

Вероятность ошибки в канале

Вероятность ошибки в канале

Рис. 5. Результаты декодирования П-СМПП-кодов: а — алгоритм декодирования А^; б — алгоритм декодиро-