Практическое занятие №6 Изучение примеров помехоустойчивых кодов

Цель занятия: практическое исследование показательных примеров помехоустойчивых кодов.

Краткие теоретические сведения

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

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

Известны два основных класса помехоустойчивых кодов – блочные исверточные [1]. Блочные коды характеризуются тем, что биты каждого из их-разрядных слов являются функциямитолько отинформационных битов, представляемых соответствующим словом, которое при этом называетсяблоком.Сверточные коды отличаются от блочных тем, что они обладаютпамятью, т. е. биты их некоторого-го-разрядного слова являются функциями от битов как-го-битового фрагмента исходной двоичной последовательности, так и, в общем случае,предыдущих-разрядных фрагментов этой последовательности ипредыдущих-битовых фрагментов результата кодирования. Здесь– некоторое целое положительное число, зависящее от конкретной разновидности сверточного кода. Значениеназывается при этомдлиной кодового ограничения (по-английски –constraint length). Сверточный код с разрядностью кодового слова, разрядностью соответствующего ему фрагмента исходной двоичной последовательностии длиной кодового ограниченияв литературе часто обозначается как сверточный код (,,), например, код (2, 1, 3) (см. далее).

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

Блочное кодирование характеризуется следующими основными особенностями [1]:

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

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

так, например, при кодировании блочным кодом БЧХ [1] для обнаружения до 4-х ошибок в блоке разрядностью 15 бит в нем должно содержаться 7 информационных и 8 избыточных (контрольных) битов, а при разрядности блока, равной 255 битов – 239 информационных и 16 контрольных битов соответственно. Таким образом, в первом случае информационные биты составляют 46,7% от общей разрядности блока, а во втором – 93,7%.

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

Как следует из перечисленных свойств блочного и сверточного кодирования, рациональной (и реально применяемой) является обобщенная операционная модель помехоустойчивого кодирования/декодирования данных в ФКС, представленная на рис. 6.1. Блоки, обозначенные на нем пунктирной линией, могут отсутствовать в ряде практических случаев, т. к. некоторые типы ФКС и способов модуляции не требуют применения сверточного кодирования (см. далее).

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

ARQ – автоматический запрос повторной передачи (Automatic Repetition reQuest)

Рис. 6.1. Обобщенная операционная модель помехоустойчивого кодирования/декодирования данных в ЦКС

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

Описанная комбинация сверточного и блочного кодирования позволяет рационально решить проблему помехоустойчивого обмена данными между абонентами ФКС при относительно высоких изначальных значениях BERЦКС, порядка 10^-3– 10^-4. Это имеет место, например, в беспроводных ЦКС. В самом деле, при указанных порядкахBERприменение только блочного кодирования (обеспечивающего эффективное обнаружение ошибок, но обычно не позволяющего достоверно их исправлять) привело бы к недопустимому снижению скорости обмена из-за необходимости частого повторения передачи кадров, в которых обнаружены ошибки. С другой стороны, использование только сверточного кодирования привело бы к недопустимо высокому количеству пропущенных ошибок в принятом кадре из-за ограниченных возможностей сверточных кодов по обнаружению и исправлению искаженных битов. Таким образом, сверточное и блочное помехоустойчивое кодирование рационально дополняют друг друга при относительно высоких уровняхBER, обусловленных шумами в ЦКС или/и его ограниченной полосой пропускания.

Следует также отметить, что при относительно небольших изначальных значениях BER, порядка 10^-5и менее, помехоустойчивый обмен данными, как правило, обеспечивается посредством только блочного кодирования, без применения сверточного. При таких порядкахBERчастота повторений передачи кадров (из-за обнаружения ошибок в них) невысока, и эти повторения не приводят к существенному снижению скорости обмена. В частности, только блочное помехоустойчивое кодирование, без его дополнения сверточным, применяется в кабельных ЦКС ЛВС.

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

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

Форматблока ЦИК следующий:mмладших битов являются контрольными, аkстарших – информационными. Общая разрядность блока равна.Контрольные разрядыЦИК формируются какостаток от деления двух двоичных полиномов: информационного и образующего. Первый из них при этом являетсяполиномиальным представлением сдвинутого наmразрядов влево информационного поля блока, а второй – аналогичным представлением некоторой двоичной константы, оговариваемой протоколом кодирования (сущность полиномиального представления двоичных чисел и правила выполнения основных математических операций над двоичными полиномами будут изложены ниже).Синдром ошибкивычисляется как остаток от деления полинома, соответствующего принятому блоку, на образующий полином, идентичный применявшемуся при кодировании. При отсутствии ошибок в блоке все биты синдрома равны нулю. Позиции ошибочных битов могут быть определены на основе предварительно составленной таблицы синдромов.

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

Полиномиальное представление некоторого n-битового двоичного кода имеет следующий вид:

n

P(x) =b_jx^j, (6.1)

j= 0

где b_j– состояниеj-го бита данного кода.

Например, двоичное число 10111 представляется полиномом x⁴+x²+x+ 1.

При помехоустойчивом кодировании посредством ЦИК используются следующие математические операциинад двоичными полиномами: сложение двух полиномов по модулю 2, умножение полинома на х^P(где р – целое положительное число), перемножение полиномов, вычисление остатка от деления двух полиномов.

Сложениедвух двоичных полиномов по модулю 2 выполняется по следующему правилу:

s

P₁(x)Р₂(х) =(b_1j b_2j)x^j, (6.2)

j= 0

где b_1j иb_2j– коэффициенты при членах степени j полиномов P₁(x) и Р₂(х) соответственно;

s– наибольший из порядков полиномовP₁(x) и Р₂(х).

При этом нетрудно заметить, что двоичное число, соответствующее полиному Р(х), является результатом поразрядного суммирования по модулю 2 чисел, представляемых полиномами P₁(x) и Р₂(х). Например, сумма по модулю 2 полиномов x⁴+ x²+ x + 1 и x³+ x²+ 1 равна x⁴+ x³+ x.

Умножение двоичного полинома на х^P ( где р – целое положительное число) выполняется аналогично подобной операции над обычными полиномами. Например, результат умножения полинома x⁴+ x²+ x + 1 на x³равен x⁷+ x⁵+ x⁴+ x³. Заметим, что эта операция соответствует логическому сдвигу двоичного числа, представляемого полиномом, на р разрядов влево.

Произведениедвух полиномов вычисляется в соответствии с выражением:

P₁(x)*P₂(x) = P₁(x)b_2S x^S  P₁(x)b_2(S-1) x^S-1 … P₁(x)b₂₁ xP₁(x)b₂₀, (6.3)

где s– порядок полиномаP₂(x);

b_2j(j= 0,s) – коэффициент при членеj-й степени полиномаP₂(x).

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

1. Начальное значение остатка устанавливается равным делимому.

2. Если степень остатка меньше степени делителя – окончание вычисления. Если нет – переход к пункту 3.

3. Делитель умножается на х ^r-d, гдеrиd– степени остатка и делителя соответственно. Результат умножения суммируется по модулю 2 с остатком, после чего последний устанавливается равным полученной сумме. Переход к пункту 2.

Данный алгоритм будет далее пояснен конкретным примером.

Существует несколько типов ЦИК, различающихся между собой количеством и характером обнаруживаемых или исправляемых ошибок в пределах блока, а следовательно - кодовым расстоянием, правилами выбора количества контрольных разрядов и образующего полинома. Из них одними из наиболее универсальных являютсяЦИК БЧХ (Боуза – Чоудхури – Хоквинхема), позволяющие:

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

- обнаружить факт наличия до 2е ошибочных битов в блоке.

Общее количество битов в блоке ЦИК БЧХ выбирается из ряда чисел, удовлетворяющих условию:

n = 2^h – 1, (6.4)

где h – целое положительное число.

Образующий полином ЦИК рассматриваемого типа представляет собой произведение е неприводимых полиномов (т. е. не разлагаемых на полиномы более низких порядков), выбираемых по специальным таблицам, в зависимости от значений hие. Образующие полиномы ЦИК БЧХ для значенийhие,лежащих в пределах от 3 до 8 и от 2 до 8 соответственно, приведены в таблице 6.1. Необходимые данные для нахождения образующих полиномов ЦИК с более высокимиhиепредставлены в [4]. Количество контрольных разрядов ЦИК БЧХ равно степени образующего полинома, причем оно не превышает произведенияhe.

Таблица 6.1 – Образующие полиномы ЦИК БЧХ

h	e	Образующий полином	Формат блока
			n	m
1	2	3	4	5
3	2	(x^3+x+1)(x^3+x^2+1)	7	6
4	2 3 4	(x^4+x+1)(x^4+x^3+x^2+x+1) (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1) (x^4+x+1)(x^4+x^3+x^2+x+1)(x^2+x+1)(x^4+x^3+1)	15	8 10 14
5	2 3 4 5 6	(x^5+x^2+1)(x^5+x^4+x^3+x^2+1) (x^5+x^2+1)(x^5+x^4+x^3+x^2+1)(x^5+x^4+x^2+x+1) (x^5+x^2+1)(x^5+x^4+x^3+x^2+1)(x^5+x^4+x^2+x+1)(x^5+x^3+x^2+ +x+1) (x^5+x^2+1)(x^5+x^4+x^3+x^2+1)(x^5+x^4+x^2+x+1)(x^5+x^3+x^2+ +x+1)(x^5+x^4+x^2+x+1) (x^5+x^2+1)(x^5+x^4+x^3+x^2+1)(x^5+x^4+x^2+x+1)(x^5+x^3+x^2+ +x+1)(x^5+x^4+x^2+x+1) (x^5+x^4+x^3+x+1)	31	10 15 20 25 30
6	2 3 4 5 6	(x^6+x+1)(x^6+x^4+x^2+x+1) (x^6+x+1)(x^6+x^4+x^2+x+1)(x^6+x^5+x^2+x+1) (x^6+x+1)(x^6+x^4+x^2+x+1)(x^6+x^5+x^2+x+1)(x^6+x^3+1) (x^6+x+1)(x^6+x^4+x^2+x+1)(x^6+x^5+x^2+x+1)(x^6+x^3+1)(x^3+ +x^2+1) (x^6+x+1)(x^6+x^4+x^2+x+1)(x^6+x^5+x^2+x+1)(x^6+x^3+1)(x^3+ +x^2+1)(x^6+x^5+x^3+x^2+1)	63	12 18 24 27 33
7	2 3 4 5 6 7	(x^7+x^3+1)(x^7+x^3+x^2+x+1) (x^7+x^3+1)(x^7+x^3+x^2+x+1)(x^7+x^4+x^3+x^2+1) (x^7+x^3+1)(x^7+x^3+x^2+x+1)(x^7+x^4+x^3+x^2+1)(x^7+x^6+x^5+ +x^4+x^2+x+1) (x^7+x^3+1)(x^7+x^3+x^2+x+1)(x^7+x^4+x^3+x^2+1)(x^7+x^6+x^5+ +x^4+x^2+x+1)(x^7+x^5+x^4+x^3+x^2+x+1) (x^7+x^3+1)(x^7+x^3+x^2+x+1)(x^7+x^4+x^3+x^2+1)(x^7+x^6+x^5+ +x^4+x^2+x+1)(x^7+x^5+x^4+x^3+x^2+x+1)(x^7+x^6+x^4+x^2+1) (x^7+x^3+1)(x^7+x^3+x^2+x+1)(x^7+x^4+x^3+x^2+1)(x^7+x^6+x^5+ +x^4+x^2+x+1)(x^7+x^5+x^4+x^3+x^2+x+1)(x^7+x^6+x^4+x^2+1)* *(x^7+x+1)	127	14 21 28 35 42 49