Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Систематические коды






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

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

    1. В число исходных комбинаций не должна входить нулевая.

    2. Кодовое расстояние между любыми парами исходных комбинаций не должно быть меньше d min.

    3. Каждая исходная комбинация, как и любая ненулевая разрешенная комбинация, должна содержать количество единиц не менее d min.

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

    Исходные комбинации могут быть получены с помощью производящей матрицы. Производящая матрица содержит k строк и n столбцов. Она позволяет получить все возможные комбинации кода путем суммирования по модулю два (mod2) всех возможных сочетаний строк.

    По производящей матрице строится проверочная матрица, которая служит для создания алгоритмов кодирования и декодирования, а следовательно, кодирующего и декодирующего устройства.

    Производящую матрицу образуют путем приписывания справа к единичной квадратной матрице J размера k (информационной матрице) дополнительной матрицы D, содержащей n - k столбцов и k строк, например:

     

     

     

    Требования к дополнительной матрице:

    1. Количество единиц в строке должно быть не менее d –1 (одна 1 содержится в строке единичной матрицы).

    2. Сумма по mod2 двух любых строк должна содержать не менее d –2 единиц(2 единицы содержатся в сумме по mod2 двух строк единичной матрицы).

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

    1. Строится подматрица, являющаяся транспонированной по отношению к дополнительной матрице:

     

     

    1. Справа к ней приписывается единичная квадратная матрица размера n - k:

     

     

    Единицы в каждой строке проверочной матрицы соответствуют символам кода (), сумма которых по mod2 должна быть равна 0.

    Рассмотрим пример построения кода, исправляющего одиночные ошибки t =1 и имеющего n =7. Определяем кодовое расстояние d =2 t +1=3. Полное число одиночных ошибок равно 7, т.е. Е 1 = n. Число проверочных символов r вычислим по формуле:

    n - k .

    Откуда следует и соответственно, число информационных символов k =4.

    Строим производящую матрицу, содержащую k - строк, n - k - столбцов. Вид производящей матрицы зависит от вида дополнительной матрицы D.

     

    и т.д.

     

    Возьмем, например, дополнительную матрицу D , тогда производящая матрица А 7, 4 будет иметь следующий вид:

     

     

    Определяя суммы по mod2 всех возможных сочетаний строк производящей матрицы, получим 2 k -1 ненулевых комбинаций систематического кода, используемых для передачи кодированных информационных сообщений:

     

    1 2=1100110

    1 3=1010101

    ……………….

    1 2 3 4=1111111.

     

    Всего имеем таким образом 15 комбинаций.

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

     

     

    Строки дополнительной матрицы являются столбцами транспонированной матрицы .

    Из Н получаем следующие уравнения проверки для 1, 2 и 3-ей строк:

     

      r 1= a 2 a 3 a 4 a 5=0, r 2= a 1 a 3 a 4 a 6=0, r 3= a 1 a 2 a 4 a 7=0.  

     

    Анализ этих уравнений показывает, что:

     

    элемент а 1 входит в уравнение 2 и 3;

    элемент а 2 входит в уравнение 1 и 3;

    элемент а 3 входит в уравнение 1 и 2;

    элемент а 4 входит в уравнение 1, 2, 3

    и т.д.

    Следовательно, искажение одного из элементов аi нарушает вполне определенные уравнения, по которым можно определить и восстановить искаженный элемент.

    Составим таблицу 1 восстановления искаженных символов.

    Таблица 1

    Соответствие номеров искаженных символов уравнениям проверок

    Уравнения проверок № искаженного элемента
    a 1 a 2 a 3 a 4 a 5 a 6 a 7
    r 1              
    r 2              
    r 3              

     

    Если r i = 0, то уравнение не нарушено и искаженных символов нет, если ri = 1, уравнение нарушено и имеется искаженный символ.

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

     

    из r 1 получим a 5= a 2 a 3 a 4,

    из r 2 получим a 6= a 1 a 3 a 4,

    из r 3 получим a 7= a 1 a 2 a 4.

     

    Пусть источник выдает сообщение в виде кода 1011, которому соответствуют символы (а 1а 4), кодирующее устройство добавляет символы a 5 =0, a 6 =1 и a 7=0. В результате формируется кодовая комбинация 1011010 (а 1а 7), которая передается по каналу. Если на приемной стороне получили искаженную комбинацию 1010010, то решение уравнений проверок:

     

    r 1= a 2 a 3 a 4 a 5=1

    r 2= a 1 a 3 a 4 a 6=1

    r 3= a 1 a 2 a 4 a 7=1

    покажет, что исказился элемент а 4, т.к. он входит во все уравнения проверок.

    Кодовая комбинация вида Rj = r 1, r 2, …, rn - k называется контрольной последовательностью, опознавателем или синдромом ошибки.

     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.