Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Самокорректирующиеся коды. Коды Хемминга.↑ ⇐ ПредыдущаяСтр 2 из 2 Содержание книги
Поиск на нашем сайте
Цель работы: изучение общих методов формирования кодов, получение практических навыков по формированию корректирующих кодов на примере построения и декодирования систематического кода и изучение его свойств. Задание. Обнаружить и исправить ошибку в представленном коде, декодировать сообщение.
Краткие теоретические сведения. Каждое слово сообщения A при равномерном кодировании допускает разложение вида A =Ai1,Ai2 ,Ai3,…Ain, и имеет единственное такое разложение. Если ограничиться бинарным кодированием, то Ai = a1 a2 a3…..am номера слов в словаре, записанные в двоичной системе (ai принимает значения 0 или1). Необходимо отметить, что каждый двоичный номер слова может быть однозначно записан и десятеричным числом. Пусть S”(I) – подмножество всех слов, допускающих разложение указанного вида. Рассмотрим следующую схему кодирования: A1® B1 A2® B2 A3® B3 (2.1) …. As® Bs, где Bi = b1 b2 b3 …bl – элементарные двоичные коды, имеющие одинаковую длину l = m + k, при этом такие, чтобы по коду, полученному на выходе канала связи (помеха может изменить 0 на 1 или наоборот, но не может добавить или убрать элемент bi) однозначно восстановить код на входе канала и из него получить исходное сообщение.
Построение самокорректирующихся кодов было осуществлено Хеммингом. Рассмотрим случай, когда источник помех может внести не более одного инвертирования в элементарный код Bi (р =1). Вариантов получения элементарного кода Bi будет l +1 (правильный и l штук с инвертированием bi на каждой позиции). Для того, чтобы дополнительных разрядов в коде Bi хватило для кодирования l +1 случаев, необходимо выполнение следующего условия: 2 m ≤ 2 l / (l + 1) (2.2) Из этих соображений выбираем l как наименьшее целое число, удовлетворяющее неравенству (2). Дальнейшее построение будет состоять из трех этапов: 1. Построение кодов Хемминга (описание алгоритма кодирования). 2. Обнаружение ошибок в кодах Хемминга. 3. Декодирование.
Построение кодов Хемминга (описание алгоритма кодирования) В множестве натуральных чисел {1,2,3,…, l }выделим следующие подмножества: 1, 3, 5, 7, 9 ….(содержатся все числа, у которых при переводе в двоичную запись в последнем разряде 1); 2, 3, 6, 7, 10 ….(содержатся все числа, у которых при переводе в двоичную запись в предпоследнем разряде 1); .......... 2k–1, 2k–1 +1, ….(содержатся все числа, у которых при переводе в двоичную запись в k –ом, считая справа, разряде 1). Наименьшие члены этих подмножеств являются степенями 2: 1 = 20; 2 = 21; 4 = 22;…., причем 2k–1 ≤ l, а 2k+1 ³ l +1. Члены bi набора b1 b2 b3 …bl, у которых индекс i принадлежит множеству {1, 2, 4,… 2k–1}, называются контрольными членами, остальные – информационными. Таким образом, контрольных членов будет k, а информационных l – k = m. Сформулируем правило построения набора …bl по набору a1 a2 a3…..am. Сначала определяются информационные члены: b3 = a1 b5 = a2 b6 = a3 ..... Таким образом, набор информационных членов, расположенных в естественном порядке, совпадает с набором a1 a2 a3…..am. Затем определяются контрольные члены, b1 = b3+ b5 + b7 + … (mod 2), b2 = b3+ b6 + b7 + … (mod 2), (2.3) b4= b3+ b6 + b7 + … (mod 2), .............
значения которых 0 или 1 и помещаются на соответствующих местах в элементарных кодах Bi. По сути, создается кодовый словарь для схемы кодирования (1), в котором для каждого элементарного кода выполняются следующие условия (суммирование по mod 2): b1 + b3+ b5 + b7 +…= 0, b2 + b3+ b6 + b7 + … = 0, (2.4) b4 + b3+ b6 + b7 + … = 0, ............. (количество единиц в позициях элементарного кода, определяемых индексами, четно).
Обнаружение ошибок в кодах Хемминга Ошибка на выходе из канала связи может быть обнаружена и исправлена так (для построенного кода – не больше одной в каждом элементарном коде). Номер позиции S (записанный в двоичной системе), в которой произошла ошибка, определяется так: S = Sk… S2 S1 , где Si определяется по формулам (4) для элементарного кода, полученного на выходе канала связи. Если ошибки нет, то Si = 0 и общий результат S = 0.
Пример 1: Пусть на вход канала связи поступил элементарный код 0110011 (т.е закодировано **1*011 (поз. 3,5,6,7– информационные, а контрольные члены заменены *)). На выходе получено 0110001 (искажен 6–й член элементарного кода). Вычислим S. S1 = b1 + b3+ b5 + b7 = 0 + 1 + 0 + 1 = 0 (mod 2), S2 = b2 + b3+ b6 + b7 = 1 + 1 + 0 + 1 = 1 (mod 2), S3 = b4 + b5 + b6 + b7 = 0 + 0 + 0 + 1 = 1 (mod 2). S = 1 1 0 = 6 (в десятичной системе). Пример 2: Пусть на выходе получено 0111011 (искажен 4–й (контрольный) член элементарного кода). S1 = b1 + b3+ b5 + b7 = 0 + 1 + 0 + 1 = 0 (mod 2), S2 = b2 + b3+ b6 + b7 = 1 + 1 + 1 + 1 = 0 (mod 2), S3 = b4+ b5 + b6 + b7 = 1 + 0 + 1 + 1 = 1 (mod 2). S = S3 S2 S1= 1 0 0 = 4 (в десятичной системе). Тогда восстановленное сообщение имеет вид: 0110011, а исходное сообщение – 1011 (удалены контрольные члены, выделенные цветом) Декодирование После получения закодированного сообщения происходит его разбивка на элементарные коды, вычисление для каждого кода S и в случае его неравенства 0 – корректировка соответствующего информационного члена (если S указывает на контрольный член, то корректировка не нужна). После удаления всех контрольных членов получаем исходное сообщение.
Примечание: Рассмотрено построение кодов Хемминга для бинарного кодирования и допустимом числе ошибок в элементарных кодах не более одной. Существует теория для построения таких кодов для равномерного кодирования любой арности и числе ошибок не более 2, 3,… и. д. Лабораторная работа №3 Формальные грамматики и языки|речь|. (Цепочки. Классификация грамматик по Хомскому).
Цель работы: закрепить понятия « алфавит», «цепочка», «формальная грамматика» и «формальный язык», «выводимость цепочек», «эквивалентная грамматика»;сформировать умения и навыки распознавания типов формальных языков и грамматик по классификации Хомского, построения эквивалентных грамматик.
Задание. 1.Определить к какому типу по Хомскому относится данная грамматика, какой язык она порождает, каков тип языка. 2.Указать максимально возможный номер типа грамматики и языка.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-26; просмотров: 906; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.255.198 (0.008 с.) |