30-40_рк1 (Ответы к рубежным контролям)

30. Коды коррекции ошибок. Итеративный подход

Итеративные коды могут строиться на основе использова­ния двух, трехмерных матриц (таблиц) и более высоких размерностей. Установим основные соотношения между парамет­рами (характеристиками) двумерного итеративного кода, когда используются исходные помехоустойчивые коды (n₁,k₁,d₀₁) и (n₂,k₂,d₀₂); в общем случае данные исходные коды могут иметь как одинаковые параметры, так и разные, т.е. и или наоборот.

Из способа формирования двумерного итеративного кода (рис.4.1) следует:

– общее количество двоичных символов в кодо­вой последовательности итеративного кода;

– общее количество информационных символов в кодовой последовательности N_u итеративного кода;

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

studru728head

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

Если исходные помехоустойчивые коды корректируют соответственно t₁ и t₂ ошибочных символов, то двумерный итеративный код обеспечивает исправление

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

где t_n1 и t_n2 -кратности пакетов ошибок, корректируемые соответственно исходными кодами (n₁,k₁,d₀₁) и (n₂,k₂,d₀₂)

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

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

Вероятность ошибочного декодирования информации при использовании двумерного итеративного кода приближенно рас­считывается как

где Р_{ош.дек.1} и Р_{ош.дек.2} – вероятности ошибочного декоди­рования исходных помехоустойчивых кодов соответственно (n₁,k₁,d₀₁) и (n₂,k₂,d₀₂).

Пример: код (n,k)=(24,16)

Таблица кодирования для k=16 имеет вид:

а₁-а₁₆ – информационные символы

b₁-b₈ – проверочные символы

При (а₁-а₁₆)=(1110 1001 1000 0010), (b₁-b₈)=(1011 1101) таблица

Достоинствами итеративных кодов являются:

1. вы­сокая корректирующая способность (даже при вероятности ошибок в канале связи Р_k=0,5),

2. выбором соответствующего количества исходных помехоустойчивых ко­дов и их параметров можно обеспечить малую вероятность оши­бочного приема информации, т.е минимальную вероятность ошибок декодера Р_ош.дек.;

3. минимальная сложность аппаратной и программной реализации;

4. возможность защиты информации от несанкционированного доступа и др.

Недостатками данных кодов являются:

1. большая избыточность кодов;

2. большая задержка информации при декодировании;

3. высокая сложность реализации систем цикловой синхронизации распределителей информации кодека и др.

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

31. Коды коррекции ошибок. Каскадный подход

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

Например, популярной является следующая конструкция: данные кодируются кодом Рида-Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.

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

32. Коды коррекции ошибок. Турбо код

Ту́рбо-код — параллельный каскадный блоковый систематический код, способный исправлять ошибки, возникающие при передаче цифровой информации по каналу связи с шумами. Синонимом турбо-кода является известный в теории кодирования термин — каскадный код (англ. concatenated code) (предложен Д. Форни в 1966 году).

Турбо-код состоит из каскада параллельно соединённых систематических кодов. Эти составляющие называются компонентными кодами. В качестве компонентных кодов могут использоваться свёрточные коды, коды Хемминга, Рида — Соломона, Боуза — Чоудхури — Хоквингема и другие. В зависимости от выбора компонентного кода турбо-коды делятся на свёрточные турбо-коды (англ. Turbo Convolutional Codes, ТСС) и блоковые коды-произведения (англ. Turbo Product Codes, TPC)^[1].

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

Структура турбо-кода

Согласно Шеннону, наилучшим кодом является код, который передает сообщение за бесконечно большое время, формируя в каждый момент времени случайные кодовые элементы. У приёмника есть бесконечные версии сообщения, искажённого случайным образом. Из этих копий декодер должен выбрать копию, наиболее близкую к переданному сообщению. Это представляет собой теоретически идеальный код, который может исправить все ошибки в сигнале. Турбо-код является шагом в этом направлении. Ясно, что мы не должны посылать информационное сообщение в течение бесконечного времени. Для приемлемой работы достаточно удвоить или утроить время передачи, что обеспечит довольно приличные результаты для каналов связи.

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

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

Существует несколько схем турбо-кодов:

• PCCC — в случае конкатенации параллельных сверточных кодов

• SCCC — схема с последовательным соединением сверточных кодов, коды SCCC имеют высокие характеристики при больших отношениях сигнал/шум

• TPC — турбо-код-произведение, использует блочные коды вместо сверточных; два различных блочных кода (обычно коды Хемминга) соединены последовательно без промежуточного перемежителя. Так как два кода независимы и работают в рядах и колонках, что само по себе обеспечивает достаточно хорошую рандомизацию, то применение перемежителя не требуется.

На рис. 1 представлена общая структурная схема M-блочного турбо-кодера.

Сначала на вход формирователя пакетов PAD (англ. Packet Assembler/Disassembler) поступает блок данных длиной бит. В формирователе пакетов к данным прибавляется ещё дополнительных бит служебной информации, соответствующих используемому стандарту формирования пакета и включающих в себя символы его начала и окончания^[4]. То есть получается пакет , состоящий из бит.

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

Перемежение в турбо-кодах

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

Задача перемежителя — преобразовать входную последовательность так, чтобы комбинации бит , соответствующие кодовым словам с низким весом (весом называется число ненулевых бит кодового слова) на выходе первого кодера, были преобразованы в комбинации, дающие кодовые слова с высоким весом на выходах остальных кодеров. Таким образом кодеры получают на выходе кодовые слова с различными весами. При кодировании формируются кодовые слова так, чтобы получалось максимально возможное среднее расстояние между ними (расстоянием между двумя кодовыми словами называется число бит, в которых они различаются). Из-за того что кодовые блоки формируются из почти независимых частей, на выходе турбо-кодера среднее расстояние между кодовыми словами больше, чем минимальное расстояние для каждого компонентного кодера, а следовательно растёт эффективность кодирования.

Перестановка для каждой указанной длины блока задается определенным переупорядочиванием целых чисел как предусмотрено следующим алгоритмом (ECSS-E-ST-50-01C)^[5].

, где одному из следующих значений : , , , , в зависимости от необходимой глубины перемежителя