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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Реферат Оптимальное кодирование. Число дополнительно вводимых двоичных символов. Закодированный текст. Зависимость нижней границы допустимых значений и относительной избыточности. Конкретная конструкция кода Р. Хэмминга. Контрольная матрица. Контрольные символы.

Информация:

Тип работы: Реферат. Предмет: Схемотехника. Добавлен: 11.02.2009. Сдан: 2009. Уникальность по antiplagiat.ru: --.

Описание (план):


БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
кафедра РЭС
реферат на тему:
«Практическое кодирования по Хэммингу»

МИНСК, 2009
Пусть нам предстоит закодировать текст, записанный на некотором языке, таком, что число букв в алфавите этого языка n = 2m (m целое число), а появление в тексте тех или иных букв алфавита равновероятно и не зависит от того, какие буквы им предшествовали. Тогда имеем
p(i) = p(j) = 1/n; H = log2 = m.
Условия задачи таковы, что достичь оптимального кодирования можно самым незатейливым методом кодирования - побуквенным кодированием с постоянной длиной (l = m) кодовых наборов. При этом, однако, мы оказались бы лишенными какой-либо возможности обнаруживать, а тем более исправлять ошибки. Чтобы такая возможность появилась, необходимо отказаться от оптимальности кода, "раскошелиться" на несколько дополнительных двоичных символов на букву, т.е. умышленно ввести некоторую избыточность, которая смогла бы помочь нам обнаружить или исправить ошибки. Необходимое число дополнительно вводимых двоичных символов на одну букву обозначим через x, и тогда длина кодового набора станет равной l = m + x. Примем, что в результате помех (случайных или преднамеренных) лишь один или вовсе никакой из m + x двоичных символов может превращаться из единицы в нуль или, наоборот, из нуля в единицу. Примем далее, что 1 + m + x событий, заключающиеся в том, что ошибка вообще не произойдет, произойдет на уровне первого, второго, .... (m + x)-го символа кодового набора, равновероятны. Энтропию угадывания того, какое именно из этих 1 + m + x событий будет иметь место, в силу равновероятности этих событий можно определить по формуле Н = log2 (1 + m + х) бит. Таким образом, для обнаружения самого факта наличия одиночной ошибки и установления ее позиции необходимо заполучить информацию в количестве не менее Н = log2(1 + m + x) бит. Источником этой информации служат лишь дополнительно введенные x двоичных символов, так как остальные m символов из-за оптимальности кодирования до предела заняты описанием самого текста. Заметим, что x двоичных символов в лучшем случае могут содержать информацию в количестве x бит. Таким образом, при конструировании кода, обнаруживающего и исправляющего одиночную ошибку, следует учесть, что этого можно добиться лишь при значениях x, удовлетворяющих неравенству
х>= log2(l+m+x),
или 2x-x-1>=m.
Рис. 1.Зависимость нижней границы допустимых значений x от m (сплошная линия) и зависимость относительной избыточности от m (пунктирная линия).
Р. Хэмминг разработал конкретную конструкцию кода. которая обеспечивает весьма элегантное обнаружение и исправление одиночных ошибок при минимально возможном числе дополнительно вводимых двоичных символов, т.е. при знаке равенства. Проследим за построением этого кода, когда m = 4. Из рисунка следует, что при этом допустимое значение x равно трем, т.е. при числе основных (информационных) двоичных символов m = 4, число дополнительно введенных, т.е. контрольных символов должно быть не менее трех. Примем, что нам удалось "обойтись" именно тремя дополнительными символами, т.е. удалось сконструировать такой код, при котором каждый из дополнительно введенных трех символов дает нам максимально возможное количество информации, т.е. по одному биту. Тогда в расширенном кодовом наборе окажутся семь двоичных символов:
B1B2B3B4 B5B6B7
(информационные символы) (контрольные символы)
Поскольку символы B1 - B4 заняты кодированием собственно текста, то управлять их значениями нам не дано. Что же касается символов B5 - B7, то они предназначены именно для обнаружения и исправления ошибок и поэтому их значения мы можем увязать со значениями информационных символов произвольными тремя функциями от аргументов B1 - B4:
B5=B5(B1,...,B4) (1)
B6=B6(B1,...,B4) (2)
B7=B7(B1,...,B4) (3)
такими, чтобы в последующем с помощью трех других функций от аргументов B1 - B7
e0=e0(B1-B7) (4)
e1=e1(B1-B7) (5)
e2=e2(B1-B7) (6)
определить значения e0,e1,e2 содержащие информацию о том, произошла ли ошибка вообще и если да, то на уровне какого именно из семи символов. Очевидно, имеется множество различных вариантов при выборе функций (1)- (6). Р. Хэмминг поставил перед собой задачу выбора именно такой совокупности функций (1) - (6), чтобы набор значений e2e1e0 оказался двоичной записью позиции, где произошла ошибка. В случае же, когда ошибка не имела места, набор e2e1e0 должен указать на нулевую позицию, т.е. на несуществующий символ B0. Из двоичной записи этих позиций
000 (0) 1 0 0 (7)
001 (1) 1 0 1 (8)
010 (2) 1 1 0 (9)
011 (3) 1 1 1 (10)
легко уследить, что значение e0 "несет ответственность" за позиции B1, B3, B5 и B7 и поэтому в качестве функции (1.14) берется зависимость
e0 = B1+B3+B5+B7 mod 2. (11)
Аналогично, обращая внимание на то, что значения e1 и e2 отвечают за соответственно B2 B3 B6 B7 , B4 B5 B6 B7, получим
e1= B2+B3+B6+B7 mod 2, (12)
e2= B4+B5+B6+B7 mod 2. (13)
Обратим внимание, что систему (1.14а) - (1.16а) можно рассматривать как развернутую запись матричного уравнения
B1
B2
e0 1010101 B3
e1 = 0110011 B4
e2 0001111 B5
B6
B7
или
Ve=AVa,
где Ve, - вектор ошибки, указывающий на ее месторасположение; А - основная матрица, столбцы которой суть двоичные записи чисел от одного до семи.
Операция сложения во всех трех уравнениях (14) - (16) осуществляется по модулю два. Подставляя в систему уравнении (14) - (16) e0=e1=e2=0, получим систему из трех уравнений
B1+B1+B5+B7=0 mod2 (14)
B2+B3+B6+B7=0 mod2 (15)
B4+B5+B6+B7=0 mod2, (16)
Приняв в качестве неизвестных величины B5, B6 и B7 получим систему из трех уравнений с тремя неизвестными:
B5+B7=B1+B3 mod2, (17)
B6+B7=B2+B3 mod2, (18)
B5+B6+B7=B4 mod2. (19)
Эта система эквивалентна одному матричному уравнению
B1
101 B5 1010 B2
011 B6 = 0110 B3 (20)
111 B7 0001 B4
или
CVe=IVi. (21)
где Ve и Vi, векторы-столбцы, координаты которых представлены соответственно контрольными и информационными разрядами; С и I - так называемые контрольная и информационная матрицы. Столбцы этих матриц суть двоичные записи номеров соответственно контрольных и информационных разрядов.
Решение системы (17) - (19), или. что то же самое, матричного уравнения (20) относительно B5, B6, B7 приводит к конкретным выражениям для функций (1) -(3):
B5=B2+B3+B4 mod2, (22)
B6=B1+B3+B4 mod2, (23)
B7=B1+B2+B4 mod2. (24)
Заметим, что сам Р. Хэмминг в качестве контрольного берет не набор символов B(m+1),B(m+2), ...B(m+x), а нaбор символов, индексы которых представляю и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.