Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Теорема о кодировании Шеннона для
Дискретного канала с помехами Если источник информации имеет энтропию H(z), а канал обладает пропускной способностью С, то: 1. Сообщение, вырабатываемое источником, всегда можно закодировать так, чтобы скорость передачи vz была близка величине vz max. И чтобы при этом вероятность ошибки в определении переданного символа была меньше заданного числа. 2. Не существует метода кодирования, позволяющего вести передачу со скоростью выше vz max и с малой вероятностью ошибки. То есть, если H’(z) ≤ C, то может быть подобран специальный код, позволяющий вести передачу с малой вероятностью ошибки. Если H’(z) > C то такого кода не существует. Очевидно, что при уменьшении скорости передачи, можно повысить достоверность, например, методом многократного повторения. Для обеспечения нулевой ошибки, кажется, что скорость передачи должна стремиться к нулю. Теорема же утверждает, что всегда можно обеспечить скорость передачи равной Vz max путем выбора подходящего ввода.
Корректирующие коды Это коды, которые позволяют обнаруживать и исправлять ошибки. n – значность кода (из скольки символов состоит данная кодовая комбинация)
N0 = 2n, n – число возможных кодовых комбинаций. Идея возможности обнаружения ошибок заключается в том, что для передачи используются не все комбинации, а только их часть N. И это значение N<N0. Используемые комбинации N называются разрешенные, а остальные N0–N – это запрещенные комбинации. Если в результате действия помех разрешенная комбинация превращается в запрещенную, то это обнаруживает наличие ошибки. Если совокупность ошибок превращает одну разрешенную комбинацию в другую разрешенную комбинацию, то такие ошибки обнаружены не будут. Примером кода, обнаружившего одиночную ошибку, является коды с контролем по четности. Сущность таких кодов состоит в следующем: К исходной кодовой комбинации добавляют 1 или 0, таким образом, чтобы количество (сумма) единиц всегда была четной. Сбой любого одного символа обнаружит ошибку. информационный
Чтобы принять сигнал правильно, надо повторить передачу. Количество символов, на которое одна кодовая комбинация отличающаяся от другой кодовой комбинации, называется кодовым расстоянием и обозначается буквой d. d0 – минимальное кодовое расстояние – минимальное количество символов, на которое кодовая комбинация отличается друг от друга.
Для того, чтобы определить кодовое расстояние достаточно просуммировать кодовые комбинации по правилам двоичного поля и подсчитать число единиц в полученном результате.
Пример: Для кода 1 А1 = 00 0 Å 0 = 0 Правила: А2 = 01 1 Å 0 = 1 четн. – 0 А3 = 10 0 Å 1 = 1 нечетн. – 1 А4 = 11 1 Å 1 = 0 Определим кодовую комбинацию А1ÅА2 Å d = 1 А3ÅА4 Å d = 1 01 01 Для кода 2 А1=000 А2ÅА4 011 А3ÅА2 101 А2=011 110 d = 2 011 d = 2 А3=101 101 110 А4=110
Ошибку можно не только обнаружить, но и исправить, если принятая кодовая комбинация ближе к исходной, чем к любой другой разрешённой комбинации.
Пример: Построим код: К коду 2 добавим два символа, повторив первых два символа получим код 3:
Код 2 А1=000 А2=011 А3=101 А4=110
Код 3
информационные разряды контрольные разряды Определим кодовое расстояние между комбинациями Строим матрицу кодовых расстояний
Пусть передаётся комбинация А3, и она содержит ошибку матрица кодовых расстояний
vx ближе всего к А3, следовательно посылалась А3 и мы ошибку исправили. Корректирующая способность кода зависит от минимального кодового расстояния d0. Если d0 = 3, то он может исправлять ошибку, то есть корректирующую способность кода можно повышать, если увеличивать минимальное кодовое расстояние.
Для построения кодов, которые обнаруживают и исправляют одиночную ошибку d0 = 3, должно выполняться неравенство: , где nи – количество информационных разрядов n – значность кода nк – количество контрольных разрядов n = nи + nк
Поэтому результаты сведем в таблицу:
Предположим, что строим код на тридцать два сообщения nи = 5, выделяем столбец nк = 4 n = 9
Расчеты можно вести по формуле. Для кода, который обнаруживает двойную ошибку, а исправляет одиночную: - значения округляются в большую сторону - до большего целого числа
Обозначим буквой: r – кратность обнаруживающих ошибок; s – кратность исправляемых ошибок; Тогда для кодов обнаруживающих и исправляющих ошибки: d0 = r + s + 1, для кодов, которые только обнаруживают ошибки d0 = n + 1, для кодов, которые только исправляют ошибки d0 = 2s + 1 (когда r > s). Если d0 r s 1 0 0 отличие комбинации 2 1 0 обнаружение одиночной ошибки 3 1 1 обнаружение одиночной ошибки и исправление одиночной ошибки 3 2 0 обнаруживающий 2-ую ошибку
Количество контрольных разрядов и значность кода для разных минимальных кодовых расстояний, связано соотношением: Для кодов, обнаруживающих все трехкратные ошибки.
количество обнаруженных ошибок Для кодов, исправляющих двойные ошибки Для кодов, исправляющих тройные ошибки: Для кодов, исправляющих S ошибок:
Пример: Требуется передавать, обнаруживающим трёхкратные ошибки, все комбинации пятизначного двоичного кода. Чему равна общая длина кода?
r – кратность обнаруживающих ошибок. s – кратность исправляемых ошибок.
nи = 5; nк = 1 + log[6 + log6] = 5 n = nи + nк = 10 Пример: Определить количество информационных разрядов кода длиной в пятнадцать символов, если код исправляет две ошибки. n=15 nи = n - nк = 15 – 7 = 8
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-12-15; просмотров: 88; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.191.26.53 (0.015 с.) |