Лекции - Теория информации. Лекция 1. Теория информации. Понятие видов информации
 Скачать 1.15 Mb.
|
Основание кода - это число различных символов кода, т.е это основание системы счисления, которую используют для кодирования. Если коды двоичные, то  . Число разрешенных кодовых комбинаций Nр для разделимых определяется из общего числа выходных последовательностей только последовательностями, соответствующими входным.   Главное, что запрещенные кодовые комбинации для передачи информации не используются.  Избыточность кода  в общем случае определяется выражением: Избыточность кода показывает, какая доля кодовых комбинаций не используется для передачи информации, а используется для повышения помехоустойчивости. Для двоичных кодов  соответственно можно выразить через: - относительная скорость кодаКодовое расстояние d - число позиций, в которых две кодовые комбинации отличаются друг от друга. Кодовое расстояние можно найти в результате сложения по модулю 2 одноименных разрядов кодовой комбинации.  Например. A=01101 B=10111 11010 → d=3  Кодовое расстояние часто называют кодом Хемминга. Кодовое расстояние между различными комбинациями конкретного кода может быть различным. Минимальное кодовое расстояние  - это минимальное расстояние между разрешенными кодовыми комбинациями данного кода.  является основной характеристикой корректирующей способности кода.Декодирование после приема может производиться таким образом, что принятая комбинация отождествляется с той разрешенной, которая находится от нее на наименьшем кодовом расстоянии. Такое декодирование называется декодированием по методу максимального правдоподобия. Например, при d=1 все кодовые комбинации называют разрешенными. Пусть n=3 , кодовые комбинации: 000, 001, 010, 100, 110, 111, 101. Любая одиночная ошибка в таком коде переводит заданную разрешенную комбинацию в другую разрешенную комбинацию. Это случай без избыточного кода, не обладающего корректирующей способностью. Если предположить, что d=2, и для n=3 сформируем набор разрешенных комбинаций: 000, 011, 101, 110 - разрешенные комбинации; 001, 010, 100, 111 - запрещенные комбинации. При этом однократная ошибка переведет кодовую комбинацию из категории разрешенных в категорию запрещенных. Этот факт позволяет обнаружить наличие ошибки. Эти ошибки будут обнаружены, если кратность их нечетная. При d=2 и более в кодах появляется корректирующее свойство. В общем случае при необходимости обнаружения ошибки с кратностью s очевидно, что  (граница обнаружения ошибки кратностью s).Для исправления одиночной ошибки в разрешенной кодовой комбинации необходимо составить подмножества кодовых комбинаций, зная, в каком подмножестве запрещенных кодовых комбинаций окажется принятая, можно точно восстановить переданную комбинацию, т.е. исправить ошибки. Рассмотрим случай, когда d=3 и n=3.  001010 100 Разрешенные кодовые комбинации 0   Запрещенные кодовые комбинации 00 111 110 101 011 Тогда по принятой комбинации 011 и факту её попадания в запрещенную кодовую комбинацию ошибка будет обнаружена, а зная, что подмножество запрещенных комбинаций соответствует разрешенной комбинации 111, мы можем исправить принятую комбинацию на разрешенную. Код при этих условиях обладает свойствами исправления ошибок. В общем случае для обеспечения возможности исправления всех ошибок кратности до t включительно при декодировании при методе максимального правдоподобия, каждая из ошибок декодирования должна приводить к запрещенной комбинации, относящейся к подмножеству исходных разрешенных кодовых комбинаций:  - граница исправления ошибок кратностью t.Общая граница обнаружения и исправления ошибок с соответствующей кратностью:  .Таким образом, задача построения помехоустойчивой корректирующей способностью сводится к обеспечению необходимого минимального кодового расстояния. Увеличение минимального кодового расстояния приводит к росту избыточности кода, при этом желательно, чтобы число проверочных символов было минимальным. Это противоречие разрешается через определение верхней и нижней границ числа проверочных символов. В настоящее время известен ряд границ, которые устанавливают взаимосвязь между кодовым расстоянием и числом проверочных символов. Кроме того, эти границы позволяют определить вероятность ошибки декодирования. Граница Хемминга находится из соотношения известного для числа разрешенных комбинаций:  , где n=k+r – число символов; t = - кратность исправляемых ошибок; - число сочетаний из n по i. Применение границы Хемминга дает результаты близкие к оптимальным для высокоскоростных кодов  > 0,3.Для низкоскоростных кодов, т.е. R =  ≤ 0,3, границу числа проверочных символов называют границей Плоткина: Граница Варшамова – Гильберта:  Таким образом, граница Хемминга и Плоткина определяют необходимое количество проверочных символов, а граница Варшамова- Гильберта достаточное их количество. Если количество проверочных символов выбрано так, что оно удовлетворяет эти границам, то код считается близким к оптимальному. Коды, в которых число проверочных символов выбирается равным границам Хемминга или Плоткина называется совершенным или полноупакованным. 5.3.Линейные (систематические) коды. 5.3.1.Механизмы кодирования и синдромного декодирования. В линейных систематических кодах информационные символы при кодировании не изменяются, а проверочные символы получаются в результате суммирования по модулю 2 определенного числа информационных символов. Запишем некоторые разрешенные кодовые комбинации систематического кода (n, k)  , где  - информационные символы;  - проверочные символы.Тогда  , где  - некоторый коэффициент принимающий значение 0 или 1 в зависимости от того, участвует или нет данный информационный символ  в формировании проверочного символа  .Обнаружение и исправление ошибок систематическим кодом сводится к определению и последующему анализу синдрома или вектора ошибок. Под синдромом понимают некую совокупность символов  сформированную, путем сложения по модулю 2 принятых проверочных символов и вычисленных проверочных символов. Вычисленные проверочные символы получаются из принятых информационных символов  по тому же правилу, которое используется для формирования проверочных символов.  Если при приеме информационных и проверочных символов (принятое считается полная кодовая комбинация, состоящая из информационных и проверочных символов) не произошло ошибок, то принятые вычисленные проверочные символы будут совпадать. В этом случае все разряды синдрома будут равны нулю. Таким образом, нулевой синдром соответствует случаю отсутствия ошибок. Если в принятых кодовых комбинациях есть ошибки, то в разрядах синдрома появятся 1. Это и есть способ обнаружения ошибок систематическим кодом, который лежит в основе синдромного декодирования. Если код имеет минимальное кодовое расстояние  , то такой код способен исправлять ошибки. Это значит, что по виду синдрома можно определить номер ошибочной позиции принятой кодовой комбинации.Процедура построения систематического кода, способного обнаруживать ошибки, сводится к выбору весовых коэффициентов так, чтобы синдром, рассматриваемый как двоичное число, указывал на номер ошибочной позиции. Пусть требуется построить систематический код длиной n=7, способный исправлять одиночные ошибки, т.е. =2t+1=3. Пользуясь условием границы Хемминга, найдем минимальное число проверочных символов: Выберем r=3, следовательно, код (7,4)- совершенный и близкий к оптимальному. Тогда кодовая комбинация  - это и есть кодовая комбинация (7,4). Для нашего случая получим: , , .Найдем весовые коэффициенты . Для этого запишем все возможные трехразрядные кодовые комбинации синдрома:000, 001, 010, 100, 011, 101, 110, 111 Если ошибки отсутствуют, то синдром должен быть нулевым. Допустим, что появление одной 1 в синдроме будет связано с ошибками в проверочных символах кодовой комбинации. Тогда 100 → ошибка в b1, 010→ ошибка в b2, 001→ ошибка в b3. Появление большего числа единиц в синдроме будет связано с ошибками в информационных символах. Теперь присвоим информационным символам с ошибками оставшиеся синдромы, причем в порядке возрастания их двоичных символов: 011→ ошибка в  ,101→ ошибка в  ,110→ ошибка в  ,111→ ошибка в  .Для определения коэффициентов их надо подобрать таким образом, чтобы при возникновении ошибки в информационном символе аi появлялся бы соответствующий этой ошибке синдром. Например, для ошибки в символе необходимо в уравнениях правила формирования проверочных символов коэффициенты при этом ошибочном символе взять соответствующими синдрому этого символа. Тогда →  =0,  = 1,  =1, → =1,  =0,  =1, → =1,  =1,  =0, → =1,  =1,  =1.Тогда по этим коэффициентам строятся уравнения формирования проверочных символов, которые будут иметь вид:  , , .
|
