Автор работы: Пользователь скрыл имя, 24 Мая 2013 в 13:44, курсовая работа
Помехоустойчивым (корректирующим) кодированием называется кодирование при котором осуществляется обнаружение либо обнаружение и исправление ошибок в принятых кодовых комбинациях.
Возможность помехоустойчивого кодирования осуществляется на основании теоремы, сформулированной Шенноном, согласно ей:
если производительность источника меньше пропускной способности канала связи, то существует по крайней мере одна процедура кодирования и декодирования при которой вероятность ошибочного декодирования сколь угодно мала, если же производительность источника больше пропускной способности канала, то такой процедуры не существует.
Принципы помехоустойчивого кодирования 3
Декодирование помехоустойчивых кодов 4
Способ сравнения. 4
Синдромный способ 4
Мажоритарное декодирование 4
Классификация корректирующих кодов 5
Код с постоянным весом 5
Код с четным числом единиц 6
Код Хэмминга 6
Матричное представление систематических кодов 10
Декодирование циклических кодов 11
Список использованной литературы: 12
1. Преобразуем комбинацию в
Ai = 0110 = х2 + х = Ai(x).
2. Находим количество
r = n – k = 7 – 4 =3
Ai(x)*xr = (х2 + х)* x3 = х5 + х4
3. Определяем остаток от деления
R(x) = Ai(x)*xr/G(x)
4. Прибавляем остаток от деления к информационным разрядам и переводим в двоичную систему счисления:
Biр(x) = Ai(x)*xr+ R(x) = х5 + х4 + 1= 0110001.
5. Преобразуем кодовую
Biр(x) = х5 + х4 + 1 = 0110001 = Biр
Как видно из комбинации четыре старших
разряда соответствуют
Формирование разрешенной кодовой комбинации неразделимого циклического кода.
Формирование данных комбинаций осуществляется умножением информационной комбинации на порождающий полином:
Biр(x) = Ai(x)*G(x).
Причем умножение можно
Пример 3: необходимо сформировать кодовую комбинацию неразделимого циклического кода используя данные примера 2, т. е. G(x) = х3+х+1, Ai(x) = 0110, код (7,4).
1. Переводим комбинацию из
Ai = 0110 = х2+х = Ai(x)
2. Осуществляем умножение Ai(x)*
3. Переводим кодовую комбинацию из полиномиальной форы в двоичную:
Bip(x) = х5+х4+х3+х = 0111010 = Bip
В этой комбинации невозможно выделить информационную и проверочную части.
Систематические коды, рассмотренные выше (код Хэмминга и разделимый циклический код) удобно представить в виде матриц. Рассмотрим, как это осуществляется.
Поскольку систематические коды обладают тем свойством, что сумма двух разрешенных комбинаций по модулю два дают также разрешенную комбинацию, то для формирования комбинаций таких кодов используют производящую матрицу Gn,k. С помощью производящей матрицы можно получить любую кодовую комбинацию кода путем суммирования по модулю два строк матрицы в различных комбинациях. Для получения данной матрицы в нее заносятся исходные комбинации, которые полностью определяют систематический код. Исходные комбинации определяются исходя из условий:
1) все исходные комбинации должны быть различны;
2) нулевая комбинация не должна входить в число исходных комбинаций;
3) каждая исходная комбинация должна иметь вес не менее кодового расстояния;
4) между любыми двумя исходными комбинациями расстояние Хэмминга должно быть не меньше кодового расстояния.
Производящая матрица имеет вид:
Производящая подматрица имеет k строк и n столбцов. Она образована двумя подматрицами: информационной (включает элементы аij) и проверочной (включает элементы bij). Информационная матрица имеет размеры k x k, а проверочная — r x k.
В качестве информационной подматрицы удобно брать единичную матрицу Ekk:
Проверочная подматрица Gr,k строится путем подбора различных r-разрядных комбинаций, удовлетворяющих следующим правилам:
1) в каждой строке подматрицы количество единиц должно быть не менее d0-1;
2) сумма по модулю два двух любых строк должна иметь не менее d0-2 единицы;
Полученная таким образом
При декодировании таких кодов (разделимых и неразделимых) используется Синдромный способ. Вычисление синдрома осуществляется в три этапа:
1. принятая комбинация Bip’ преобразуется их двоичной формы в полиномиальную (Bip(x));
2. осуществляется деление Bip(x) на порождающий полином G(x) в результате чего определяется синдром ошибки C(x) (остаток от деления);
3. синдром ошибки преобразуется из полиномиальной формы в двоичную;
4. По проверочной матрице или
таблице синдромов
5. Ошибочный разряд в Bip’(x) инвертируется;
6. Исправленная комбинация
делением принятой кодовой комбинации Biр’(x) на порождающий полином G(x), который заранее известен на приеме. Остаток от деления и является синдромом ошибки С(х).