Реферат: Практическое кодирования по Хэммингу - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Практическое кодирования по Хэммингу

Банк рефератов / Радиоэлектроника

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 28 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

БЕЛОРУССКИЙ ГОСУДАРСТВЕН НЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ кафедра РЭС реферат на т ему: «Практическое к одирования по Хэммингу » МИНСК, 2009 Пусть нам предстоит закодировать текст, записанный на некото ром языке, таком, что число букв в алфавите этого языка n = 2 m (m целое число), а появление в тексте тех и ли иных букв алфавита равновероятно и не зависит от того, какие буквы им п редшес т вовали. Тогда имее м p(i) = p(j) = 1/n; H = log 2 = m. Условия задачи таковы, что достичь оптимального кодирования можно самы м незатейл и вым методом ко дирования - побуквенным кодированием с постоянной длиной (l = m) кодовых наб оров. При этом, однако, мы оказ а лись бы лишенными какой-либо возможности обнаруживать, а тем б олее исправлять ошибки. Чтобы такая возможность появилась, необходимо о тк а заться от оптимальнос ти кода, "раскошелиться" на несколько дополнител ь ных двоичных символов на букву, т.е. у мышленно ввести некоторую изб ы точность, которая смогла бы помочь нам обнаружить или исправи ть ошибки. Необходимое число дополнительно вводимых двоичных символов на одну букву обозначим через x, и тогда длина кодового набора станет равн ой l = m + x. Примем, что в результате помех (случайных или преднамеренных) лишь один или вовсе никакой из m + x двоичных си м волов может превращаться из единицы в нуль или, наоборот, и з нуля в единицу. Примем далее, что 1 + m + x событий, заключающиеся в том, что оши бка вообще не произойдет, пр о изойдет на уровне первого, второго, .... (m + x)-го символа кодового на бора, равновероя т ны. Энтро пию угадывания того, какое именно из этих 1 + m + x событий будет иметь м е сто, в силу равновероятности эти х событий можно определить по формуле Н = log 2 (1 + m + х) бит. Таким образом, для обнар у жения самого факта наличия одиночной ошибки и уста новления ее позиции необходимо заполучить информацию в количестве не м енее Н = log 2 (1 + m + x) бит. Источником эт ой информации служат лишь дополнительно введе н ные x двоичных символов, так как остальные m символо в из-за оптимальности кодиров а ния до предела заняты описанием самого текста. Заметим, что x дв оичных символов в лучшем случае могут содержать информацию в кол и честве x бит. Таким образом, при ко нструировании кода, обнаруживающего и исправляющего одиночную ошибку, следует учесть, что этого можно д о биться лишь при значениях x, удовлетворяющих неравенс т ву х>= log 2 (l+m+x), или 2 x -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 e 0 =e 0 (B1-B7) (4) e 1 =e 1 (B1-B7) (5) e 2 =e 2 (B1-B7) (6) определить значения e 0 ,e 1 ,e 2 содержащие информацию о том, произошла ли ошибка в о обще и если да, то на уровне какого именно из семи символов. Очевидно, имеется множ е ство различных вариантов при выборе функций (1)- (6). Р. Хэмминг поставил перед собой задачу выбора именно т акой совокупности фун к ци й (1) - (6), чтобы набор значений e 2 e 1 e 0 оказался двоичной записью позиции, где произошла оши б ка. В случае же, когда ошибк а не имела места, набор e 2 e 1 e 0 должен указать на нулевую позицию, т.е. на н е существующий символ 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) легко уследить, что значение e 0 "несет ответственность" за позиции B1, B3, B5 и B7 и п о этому в качестве функции (1.14) бере тся зависимость e 0 = B 1+ B 3+ B 5+ B 7 mod 2. (11) Аналогично, обращая внимание на то, что значения e 1 и e 2 отвечают за соответс т венно B2 B3 B6 B7 , B4 B5 B6 B7, получим e 1 = B2+B3+B6+B7 mod 2, (12) e 2 = B4+B5+B6+B7 mod 2. (13) Обратим внимание, что систему (1.14а) - (1.16а) можно рассматр ивать как разве р нутую зап ись матричного уравнения B1 B2 e 0 1010101 B3 e 1 = 0110011 B4 e 2 0001111 B5 B6 B7 или V e =AV a , где V e , - ве ктор ошибки, указывающий на ее месторасположение; А - осно в ная матрица, столбцы которой суть дв оичные записи чисел от одного до с е ми. Операция сложения во всех трех уравнениях (14) - (16) осуще с т вляется по модулю два. По дставляя в систему уравнении (14) - (16) e 0 =e 1 =e 2 =0, получим сист е му из трех уравнений B1+B1+B5+B7=0 mod2 (14) B2+B3+B6+B7=0 mod2 (15) B 4+ B 5+ B 6+ B 7=0 mod 2, (16) Приняв в качестве неизвестных величины B5, B6 и B7 получи м систему из трех уравн е ни й с тремя неизвестными: B5+B7=B1+B3 mod2, (17) B6+B7=B2+B3 mod2, (18) B 5+ B 6+ B 7= B 4 mod 2. (19) Эта система эквивалентна одному матричному уравне нию B 1 101 B 5 1010 B 2 011 B 6 = 0110 B 3 (20) 111 B 7 0001 B 4 или CV e = IV i . (21) где V e и V i , векторы-столбцы, координаты которых представлены соответственно ко н трольными и информационными разрядами; С и I - так называ емые контрольная и информационная матрицы. Столбцы этих матриц суть дво и ч ные записи номеров соот ветственно контрольных и информационных разр я дов. Решение системы (17) - (19), или. что то же самое, матричного у равнения (20) относительно B5, B6, B7 приводит к конкретным выраж е ниям для функций (1) -(3): B5=B2+B3+B4 mod2, (22) B6=B1+B3+B4 mod2, (23) B 7= B 1+ B 2+ B 4 mod 2. (24) Заметим, что сам Р. Хэмминг в качестве контрольного б ерет не набор символов B(m+1),B(m+2), ...B(m+x), а нaбор символов, индексы которых представ ляют целые степени двойки. В случае, когда число контрольных символов ра вно трем, эти индексы ра в ны 2 0 =1, 2 1 = 2 и 2 2 = 4, т.е. речь идет о наборе символов B1B2B4, относительно которых решение системы (14) - (16) чрезвычайно упрощается: B1=B3+B5+B7 mod 2, B2=B3+B6+B7 mod 2, B 4= B 5+ B 6+ B 7 mod 2. Это и естественно, поскольку в данном случае вместо (17) имеем д е ло с матри ч ным уравнением B 3 1 0 0 B 1 B 5 0 1 0 B 2 = B 6 0 0 1 B 4 B 7 где контрольная матрица С всегда равна единичной ма трице. Отметив, что при указанной рекомендации Р. Хэмминга контрольная матрица всегда (независимо от m и x) оказывается равной единиц е, подро б ное обсуждение эт ой рекомендации оставим на потом, продолжая рассматривать в качестве ко нтрольных B5B6B7 а кач е стве ин формационных - B1B2B3B4. Рассмотрим, к примеру, набор информационных символов B1B2B3B4 = 1011. С помощью зави симостей (22) - (24) определим набор ко н трольных (дополнительно введенных, избыточных) символов B5B6B7 = 010. П усть ошибка произошла на уровне символа B5 т.е. вместо истинного расширенн ого кодового набора 1011 (0)10 получен код 1011 (1)10. Тогда с п о мощью зависимостей (14)- (16) найдем e 0 =1+1+1+0=1 mod 2, e 1 =0+1+1+0=0 mod 2, e 2 =1+1+1+0=1 mod2. Набор значений e 2 e 1 e 0 =101 является двоичной записью числа "пять ", т.е. указывает именно на пятую поз и цию (на символ B5), где, собственно, и произошла ошибка. Приведенная схема Р. Хэмминга по конструированию ко да, обнаруживающего и испра в ляющего одиночную ошибку, универсальна, и аналогичный код мож ет быть построен для произвольной пары значений m и x, удовл е творяющих уравнению 2 х - х - 1 = m. (25) Заметим также, что вовсе не обязательно, чтобы набор из m информ а ционных символ ов представлял собой код какой-то определенной буквы, как это имело мест о в только что рассмотренном примере. На практике сначала можно осуществ ить оптимальное (или близкое к оптимальному) кодиров а ние текста. Затем уже закодированны й текст можно делить на блоки по m двоичных символов в каждом, причем из во зможных знач е ний m = 2 x - х - 1 (х = 3, 4, ...) его конкретное значение с ледует выбирать исходя из эксплуат а ционной необходимости. При прочих равных условиях значение m д олжно быть тем меньшим, чем больше значимость информации и чем больше ур о вень помех. После выбора к онкретного значения m каждый блок из m и н формационных символов следует наращивать х = х (m) контрольн ыми символами, предназначенными для обнаружения и испра в ления одиночных ошибок в рамках дан ного блока. А теперь вернемся к рассмотрению вопроса о том, поче му Р. Хэмминг в качестве контрольных берет именно символы, индексы котор ых равны целым степеням двойки, т.е. 1, 2, 4, 8, 16,.... Во-первых, как уже об этом говори лось выше, при таком выборе контрол ь ная матрица всегда оказывается равной единице, т.е. фактически снимается вопрос решения системы (22)-(24) относительно контрольных символо в, так как ее "реш е ние" своди тся к простому переписыванию соответствующих уравнений. Но это не гла в ное, так как систему (22)-(24) при ходится решать только один раз и далее при ка ж дом акте кодирования мы пользуемся лишь системой (11) - (13) - решением сист е мы (22)-(24) о тносительно контрольных символов. При реализации процедур код и рования и декодирования на ЭВМ с ам факт, что контрольные символы разобщены (не следуют подряд друг за дру гом), создает определенные неудобства при каждом акте кодирования и деко дир о вания. Естественно по этому желание выбрать контрольные символы так о выми, чтобы они следовали подряд друг за другом, пу сть даже ценою того, чтобы один раз решить систему (14) - (16). Именно так поступа ли мы, когда вопреки р е коме ндации Р. Хэмминга взять в качестве контрольных символы B1,B2 и B4 взяли в кач е стве таковых символы B5, B6 и B7. Хотя это и вынудило нас решить систему относительно переме н ных B5, B6 и B7, но зато при каждом акте коди рования и декодирования мы смогли оперировать "пачками" контрольных сим волов, а не "выков ы ривать" и х среди информационных символов. Возникает вопрос; а всегда ли, при любом числе информационных символов м ы смогли бы поступать аналогичным образом? Нет, не смогли бы, если по-прежн ему хотим, чтобы двоичный набор символов e x-1 ,e x-2 ,...,e 0 указывал на адрес ошибки. Потому что уж е когда число контрольных символов больше трех, мы не имеем права взять в качестве контрольных последние х символов. Легко убедиться, что при этом контрольная матрица непременно оказалась бы вырожденной, т.е. значение ее детерминанта оказалась бы ра в ным нулю. Более того, даже в рассмотренном нами случае, когда чи сло контрольных символов равно трем, мы не смогли бы в качестве контроль ных взять, например, первые три символа. Во всех этих случаях опр е делители контрольных матриц (вс помним, что столбцы этой матрицы суть двоичные записи номеров выбранных нами контрольных символов) оказ ы ваются равными нулю. Пусть, например, мы выбрали в качестве кон трол ь ных не пачку символо в B5, B6, B7, а символы B1, B2, B3. Тогда нам пришлось бы иметь дело с квадратной матрицей третьего порядка, столбцы которой являются двоичными формами з а писи чисел 1, 2 и 3: 101 С = 011 . 000 Равенство нулю детерминанта этой матрицы свидетел ьствует о том, что систему (1.14б) - (1.16б) нельзя решить относительно переменных B1, B2, B3. Таким образом, при выборе среди m + x символов x контрольных следует заботит ься о том, чтобы определитель контрольной матрицы порядка x, стол б цы которой представляют собой д воичные записи номеров выбранных си м волов, не оказался равным нулю. Именно чтобы избавиться от этих забот, Р. Хэмминг рекомендует в качестве контрольных взять символы с индексами I, 2, 4, 8 и т.д. Легко обнаружить, что при таком выборе ко н трольных символов мы всегда (незави симо от их числа) будем иметь дело с единичной матр и цей. Кроме зависимости (10). на рисунке приведена также зависимость относител ь ной избыточности от m. Легк о заметить, что с увеличением m требуемый процент избыточности для обнар ужения и исправления одиночной ошибки резко уменьшается. Столь неестес т венный результат являетс я следствием искусственного, далекого от реальности допущения, что в рам ках каждого кодового набора независимо от его длины m + x может произойти н е более одной ошибки. Если же допустить возможность двух и более ошибок, т о задача их обнаружения, и тем более исправления усложняе т ся. Построить для этих случаев коды столь же элегантные, как код Р. Хэммннга для одиночной ошибки, пока не уд а лось. ЛИТЕРАТУРА 1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с. 2. Метрология и радиоизмерения в теле коммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Ф едоров и др. – М.: Высшая школа, 2001 г. – 383с. 3. Цапенко М.П. Изм ерительные информационные системы. - . – М.: Энергоатом издат, 2005. - 440с. 4. Зюко А.Г. , Кловский Д.Д., Назаров М.В., Фи нк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. – 368 с. 5. Б. Скляр. Цифров ая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пе р. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
В деревне Сидоровка был всего один стог сена, и из-за дикой популярности среди молодёжи он спрессовался до состояния ДСП.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по радиоэлектронике "Практическое кодирования по Хэммингу", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru