Главная страница
Навигация по странице:

  • Особенности декодирования.

  • Циклические коды

  • Декодирование циклических кодов

  • Построение декодированного конкретного циклического кода

  • Обнаружение и определение ошибок

  • Коды, обнаруживающие трёхкратные ошибки

  • Линейно групповые коды (ЛГК)

  • П ример

  • теория информации. ТИ (Best). Лекции по предмету "Теория информации" Красноярск 2002


    Скачать 1.06 Mb.
    НазваниеЛекции по предмету "Теория информации" Красноярск 2002
    Анкортеория информации
    Дата10.12.2022
    Размер1.06 Mb.
    Формат файлаdoc
    Имя файлаТИ (Best).doc
    ТипЛекции
    #837351
    страница12 из 12
    1   ...   4   5   6   7   8   9   10   11   12

    Декодирование кода Хэминга



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


    a1a2a3a4a5a6a7


    Пример: Послана комбинация vk = 0100101. Принятая комбинация vx = 0100111, т.е. имеется ошибка в шестом разряде Составим схему проверок.
    1) a1 + a3 + a5 + a7 = 0 + 0 + 1 + 1 = 0  S1 = 0

    2) a2 + a3 + a6 + a7 = 1 + 0 + 1 + 1 = 1  S2 = 1

    3) a1 + a5 + a6 + a7 = 0 + 1 + 1 + 1 = 1  S3 = 1
    S = 110  это двоичное число шесть, что соответствует разряду a6, следовательно, ошибка в шестом разряде.

    Для исправления одинарной и обнаружение двойной ошибки, кроме проверок по контрольным позициям проводят проверку на чётность для каждого кода. Для этого при формировании кода каждому коду в конце кодовой комбинации добавляется контрольный символ так, чтобы сумма единиц в полученной комбинации всегда была чётной.
    Особенности декодирования.
    При наличии одной ошибки проверкой на чётность можно обнаружить ошибку. Проверки по позициям укажут номер ошибочной позиции. При наличии двойной ошибки, проверка на чётность не фиксирует ошибку. Проверки по позициям укажут наличие ошибки.
    Пример: Построить код Хэминга для исправления одиночной и обнаружения двойной ошибки четырёх значного двоичного кода.

    0001 nu = 4 nk = 3
    Макет кода

    а1а2а3а4а5а6а7

    k1k20k3001k4
    Схема проверок:

    1) a1 + a3 + a5 + a7 = k1 + 0 + 0 + 1 = 0  k1 = 1

    2) a2 + a3 + a6 + a7 = k2 + 0 + 0 + 1 = 0  k2 = 1

    3) a1 + a5 + a6 + a7 = k3 + 0 + 0 + 1 = 0  k3 = 1


    11010010

    1101001k4 Количество единиц чётное, следовательно сам код
    Рассмотрим пример для vk = 01001011. Пример обнаружения единичной ошибки.


    a1a2a3a4a5a6a7


    vk = 01001011  ошибка в четвёртом разряде

    vx = 01011011


    1. Проведим проверки на чётность, которые указывают наличие одиночной ошибки.

    2. Проведим проверку по позициям.

    Составляем схему проверок

    1) a1 + a3 + a5 + a7 = 0 + 0 + 1 + 1 = 0  s1 = 0

    2) a2 + a3 + a6 + a7 = 1 + 0 + 0 + 1 = 0  s2 = 0  S = (001)  a4

    3) a1 + a5 + a6 + a7 = 1 + 1 + 0 + 1 = 1  s4 = 1
    Пример: Обнаружение двойной ошибки.
    Vk = 01001011

    Vx = 11011011


    1. Делаем проверку на чётность, число единиц чётное, следовательно, проверка ошибки не обнаруживает.

    2. Делаем проверки по позициям



    Схема

    1) a1 + a3 + a5 + a7 = 1 + 0 + 1 + 1 = 1  s1 = 1

    2) a2 + a3 + a6 + a7 = 1 + 0 + 0 + 1 = 0  s2 = 0  S = (101)

    3) a1 + a5 + a6 + a7 = 1 + 1 + 0 + 1 = 1  s3 = 1
    В этом случае S не указывает разряд ошибки, но S просто показывает, что она есть.
    Циклические коды
    Циклические коды названы так, потому что у них часть комбинаций может быть получена путём сдвига одной или нескольких комбинаций. Для проверки и обнаружения ошибок используется операции циклического сдвига. Циклические коды относятся к числу систематических кодов.

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

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

    x3x2x1x0

    Например: u(x) = x3 + x2 +1  1 1 0 1
    Построим циклический код. Образующий многочлен к(х) = х3 + х + 1 = 1011. При построении циклических кодов существует несколько приёмов.

    1. Умножим кодовый вектор u(x) на одночлен той же степени, что и образующий многочлен.

    u (x) * xn = (x3 + x2 + 1) * x3 = x6 + x5 + x3 = 1101000

    инф.. корректирующие разряды

    часть

    Чтобы уточнить значения корректирующих разрядов производят деление . Делить можно используя полиномы и значения двоичных разрядов.
    Разделим один многочлен на другой

    1 101 000 1011  001

    1 011 1101001

    1100

    1011

    1110

    1011

    1010

    1011

    001  остаток от деления - он прибавляется к исходной комбинации
    1101000

    + 001

    1101001 - искомый циклический код
    В общем виде можно записать

    , где Q(x) – частное; K(x) – остаток

    Умножим левую и правую часть k(x) и получим:

    u(x) * xn = Q(x) * K(x) + R(x)

    u(x) * xn + R(x) = Q(x) * K(x) – знак перед R(x) не имеет значение

    = F(x) – это цикловой код.
    Т.о. получается дваспособа образования циклического кода:

    1) Путём умножения одной из комбинаций информационной части кода на образующий многочлен:

    Q(x) * K(x) = I(x)
    2) Умножение заданной комбинации на одночлен и той же степени, что и выбранный образующий многочлен с добалением остатка от деления.

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

    Образующий многочлен K(x) принимает участие в образовании в каждой кодовой комбинации. Поэтому любой многочлен циклического кода делится на образующий без остатка. Если при делении обнаружен остаток, значит принятая комбинация содержит ошибку.

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

    Первый способ

    1) Образующая матрица получатся как результат слияния двух матриц: Первая - единичная повёрнутая размером nu.
    nu = 4
    Дополнительная матрица имеет nu – строк и nk – столбцов. Для определения строк дополнительной матрицы используют результаты делений последней строки первой повёрнутой матрицы на образующий многочлен.
    1 0000 … k(x)




    В качестве строк дополнительной матрицы используются остатки от деления.
    Пример: k(x) = 1011

    Рассмотрим процедуру деления
    1
    Остаток

    011

    110

    111

    101

    001

    010

    100

    00000… 1011

    1011

    01100

    1011

    1110

    1011

    1010

    1011

    001000

    1011




    В дополнительной матрице используются лишь те остатки, вес которых W = d0 – 1. d0 – минимальное кодовое расстояние. Строки образующей матрицы представляют собой первые комбинации искомого кода. Остальные комбинации получают суммированием различных сочетаниям строк.
    Второй способ

    Образующая матрица может быть построена в результате умножения элементов единичной матрицы размером nu на образующий многочлен.
    Третий способ

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


    Код

    Многочлен

    Код

    Многочлен

    11

    x + 1

    10001

    x4 + 1

    101

    x2 + 1

    10011

    x4 + x + 1

    111

    x2 + x +1

    10101

    x4 + x2 +1

    1001

    x3 + 1

    10111

    x4 + x2 +x + 1

    1011

    x3 + x +1

    11001

    x4 + x3 + 1

    1101

    x3 + x2 + 1

    11011

    x4 + x3 + x + 1

    1111

    x3 + x2 + x + 1

    11101

    x4 + x3 + x3 +1







    11111

    x4 + x3 + x2 + x + 1


    Построение декодированного конкретного циклического кода
    Код, исправляющий одиночную ошибку. d0 = 3.

    1) Расчёт соотношении между контрольными и информационными символами кода.
    nk = log((nu + 1) + log(nu + 1))
    2) Выбор образующего многочлена производится по таблице непреводимых двоичных многочленов. Образующий многочлен следует выбирать с минимальным числом элементов. Его степень должна быть больше или равна числу контрольных разрядов. Число элементов должно быть .
    Пример: Построим циклический код d0 = 3 для передачи шестнадцати сообщений.
    nu = 4 nk = 3
    k(x) = 1011 Строим единичную повёрнутую матрицу размером nu

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

    011

    110

    111

    101


    0000 1011

    1011

    01100

    1011

    1110

    1011

    101

    1+2 2+4 1+2+3+4

    1+3 3+4

    1+4 1+2+3

    2+3

    Обнаружение и определение ошибок
    Производится по остаткам деления принятого кодового вектора . Если в результате образовался остаток R(x) = 0, то комбинация принята без ошибок. Если есть остаток, то производят исправления. Для этого

    1. Определяют вес остатка

    Если WR S , где S – количество исправленных ошибок, то производят коррекцию. Для этого F(x) + R(x) и эта сумма даёт исправленную комбинацию.

    Если вес WR S , то производят циклический сдвиг F(x) влево, образуют новую комбинацию F1(x).

    Полученную комбинацию делят на обратный многочлен

    - остаток

    Если , то производят коррекцию F1(x) + R1(x), затем полученную комбинацию сдвигают вправо циклически на один разряд.
    Если , то ещё раз сдвигаем циклически влево и т.д.
    Пример: Пусть посылается комбинация u(x) = 0100111 (из обратной матрицы)

    Пусть принята комбинация F(x) = 1100111, содержащая ошибку в единичном разряде

    U(x) = 0100111 K(x) = 1011

    F(x) = 1100111 S = 1

    1 100111 1011

    1 011

    1111 R = 101

    1011 WR = 2 > S

    1001

    1011

    101

    1 001111 1011

    1 011

    1011 R1 = 1

    1011 = 1 = S  можем производить коррекцию

    01
    F1(x) + R1(x) 1001111

    1

    1001110
    Циклически сдвигаем комбинацию вправо на один разряд 0100111 – исправляется кодовая комбинация.

    Сложение двух соседних комбинаций циклического кода эквивалентно операции умножения первого слагаемого на x + 1.
    000101 две комбинации из производящей матрицы

    001010 (x2 + 1) * (x +1) = x3 + x +x2 +1 = 001111

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

    1) Выбор числа корректирующих разрядов

    nk – количество корректирующих разрядов



    Значения логарифма округряется до целых чисел в большую сторону
    Пример: nu = 2 = 4

    2) Выбор образующего многочлена. Он производится исходя из следующих соображений: для обнаружения трёхкратной ошибки надо иметь d0 = r + 1 = 3 + 1 = 4 степень обратного многочлена должна быть больше или равна четырём, т.е.
    Этот многочлен получают как произведение многочлена степени (nk - 1)т.е. 3, который позволяет обнаруживать все двойственные ошибки и многочлены первой степени (x + 1), который обнаруживают любое количество нечётных ошибок. Полученный многочлен унаследует корректирующие свойства, т.е. он будет обнаруживать одиночную и тройную ошибки, используя корректирующие свойства многочлена x + 1 и будет обнаруживать двойные ошибки, используя свойства Шеннона, например x3 + x2 +1.

    Произведём умножение

    M1 = x + 1

    M3 = x3 + x2 + 1

    M1 x M3 = (x + 1)( x3 + x2 + 1) = x4 + x2 + x +1 = k(x)

    x3 + x3 = 0 k(x) = 10111

    x3 + x3 + x3 = x3
    3) Построение образующей матрицы

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

    Пример: Строим код на четыре комбинации
    01 х к(х) = 01 x 10111 = 010111

    10 х к(х) = 10 х 10111 = 101110
    Обратная матрица


    Обнаружение ошибки

    1) Тройная ошибка
    v1 = 010111

    v k = 111011 kx = 10111

    10111

    10101 Rx = 10  обнаружена ошибка, надо повторить передачу

    10111

    0010
    2) Двойная ошибка
    v1 = 010111

    v
    Rx = 1010 – есть остаток, следовательно, посланная комбинация содержит ошибку.
    k = 110011 kx = 10111

    10111

    11101

    10111

    1010
    3) Однократная ошибка
    v1 = 010111

    v
    Rx = 1110 – есть остаток, следовательно, принятая комбинаяция содержит ошибку. Какую ошибку мы не указываем.
    k = 110111 kx = 10111

    10111

    11001

    10111

    1110
    Пример: Построить образующий многочлен для создания циклического кода, обнаруживающего все трёхкратные ошибки при передаче 1000 сообщений.
    1) Определение количества параметров кода
    nu = log2 1000 = 10

    nk 1 + log2(nu + 1 + log2(nu + 1)) = 1 + log2(11 + log211)

    nk = 5

    d0 = r + 1 = 4 – число ненулевых членов образующего многочлена
    Из таблицы нериводимых многочленов, выбираем многочлен степени nk – 1 = 4, который позволяет обнаруживать двойные ошибки.

    M4 = x4 + x + 1

    M1 = x + 1
    k(x) = M1 + M4 = (x + 1)(x4 + x + 1) = x5 + x4 + x2 + 1 110101

    Линейно групповые коды (ЛГК)
    Линейными называются коды, в которых проверочные и информационные символы связаны значениями с законами линейной комбинаторики. Т.е. с помощью определённой линейной комбинации можно построить кодовую комбинацию.

    Свойства ЛГК:

    1) Сумма (разность) кодовых векторов даёт вектор принадлежащий данному коду.

    ЛГК относят к систематическим кодам. Минимальное кодовое расстояние равно минимальному весу ненулевых кодовых векторов. ЛГК обозначается (П, nu) и задаются с помощью производящих матриц. Производящая матрица строится, как результат слияния информационной (И) и проверочной (П) матриц.



    Матрица имеет nk – столбцов и nu – строк.

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

    Вес каждой строки матрицы П WП = d0 – 1. Т.о. пораждающая матрица С приводится к следующему виду:



    Строки производящей матрицы представляют собой nu комбинации искомого кода. Остальные комбинации кода можно получить двумя способами:

    1. Их можно получить как результат сложения строк производящей матицы составленных в различных сочетаниях.

    2. ЛГК можно построить по производящей матрице, используя информационную часть кода, путём суммирования строк матрицы П.


    П ример: Построить производящую матрицу для ЛГК, способную исправлять одиночную ошибку при передачи кода на 16 сообщений.

    nu = 4; nk = log(nu + 1 + log(nu + 1)) = 3

    d0 = 3; n = 7 – значность кода

    (единичная матрица)


    Пример: Построить образующую матрицу ЛГК, способную передавать 100 сообщений и исправлять одиночную ошибку.

    N = 100 = ; nu = 7; nk = 4; n = 11;
    Строим производящую матрицу:





    Пример: Построить групповой код по заданной производящей матрице


    Выписываем информационные части кода:

    1) 0000 5) 0010

    2) 1000 6) 1010

    1. 0 100 7) 0110 и т.д.

    2. 1100 8) 1110


    К каждой информационной части строим конкретный разряд:

    1. 000

    2. 111 – берём первую строку матрицы П

    3. 110 – 2 – ю

    4. 111 – складываем первую и вторую строку

    110

    001

    1. 101

    2. 111

    101

    010 - 1 - я + 3 - я

    1. 110

    101

    011 - 2 - я + 3 - я

    1. 111

    110

    001

    100

    Декодирование ЛГК



    В процессе декодирования осуществляется проверки по определённой схеме. Число проверок равно числу контрольных разрядов. S(S1, S2, …, ) – строится проверочный вектор, который называется синдром. Если вес синдрома равен нулю, то комбинация принята правильно. Если какой – либо разряд содержит единицу, то имеется ошибка. Каждому разряду соответствует свой синдром. Вид синдрома определяется с помощью производящей матрицы. Набор синдромов содержится в специальной проверочной матрице H, которая строится из матрицы H = [ПТInk] Ink - единичная матрица. Столбцы матрицы представляют значение синдрома для каждого разряда.

    Схема проверок: принятый сигнал vx представляем в виде информационной части

    vx = (a1, a2, …,an, P1, P2,…,Pm)


    Схема проверок строится:

    1. Проверка S1

    Суммируется разряд P1 и те разряды из информационной части a1 + …+ an, номера которых совпадают с номерами ненулевых разрядов первого столбца матрицы П.

    2) Проверка S2

    Суммируется разряд P2 и те разряды информационной части a1 + …+ an, номера которых совпадают с номерами ненулевых разрядов второго столбца матрицы П.
    Пример: Задана производящая матрица C7,4 и составим схему проверок


    И П
    S1 = P1 + a2 + a3 + a4

    S2 = P2 + a1 + a3 + a4

    S3 = P3 + a1 + a2 + a3
    Строим H:



    Если разряды синдрома соответствуют одному столбцу матрицы Н, т.е. S1 = 0, S2 = 1, S3 = 1, то ошибка в первом разряде.
    Пример: Пусть имеется информационная часть ЛГК, которая исправляет одиночную ошибку. Дана производящая матрица С7,4. Получим корректирующие разряды, для этого сложим первую и вторую строку, следовательно, полный код.
    a1a2 a3a4P1P2P3

    v1 = 1100110 vx = 1101110
    Cхема проверок осталось такой же

    Проведём проверки:

    S

    1 = 1 + 1 + 0 + 0 = 0

    S2 = 1 + 1 + 0 + 0 = 0

    S3 = 0 + 1 + 1 + 0 = 0
    П

    усть vx = 1101110, т.е. ошибка в четвёртом разряде.
    S1 = 1 + 1 + 0 + 1 = 1

    S2 = 1 + 1 + 0 + 1 = 1 - это соответствует ошибке в четвёртому разряду

    S3 = 0 + 1 + 1 + 1 = 1


    Информация. Язык. Общество 2

    Измерение информации 2

    Структурный метод 2

    Статический метод 2

    Энтропия и её свойства 3

    Энтропия сложной системы 4

    Условная энтропия. Объединение зависимых систем. 4

    Полная условная энтропия 5

    Определение информационных потерь в каналах связи 6

    Энтропия и информация 8

    Взаимная информация 9

    Частная информация о системе 9

    Количественное определения избыточности 12

    Блочное кодирование 15

    Передача информации по дискретным каналам связи 19

    Код Хэминга 32

    Декодирование кода Хэминга 33

    Декодирование ЛГК 41
    1   ...   4   5   6   7   8   9   10   11   12


    написать администратору сайта