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

Реферат

Основные параметры помехоустойчивого кодирования. Основные параметры помехоустойчивых кодов

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

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

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

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

БЕЛОРУССКИЙ ГОСУДАРСТВЕ ННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ кафедра РЭС реферат на т ему: «Основные параметры помехоустойчивого кодирования. Основные параметр ы помехоустойчивых кодов» МИНСК, 2009 ОСНОВНЫЕ ПРИНЦИПЫ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАН ИЯ Кодирование с исправлением ошибок, по существу, пре дставляет с о бой метод обр аботки сигналов, предназначенный для увеличения надежн о сти передачи по цифровым каналам. Х отя различные схемы кодирования очень непохожи друг на друга и основаны на ра з личных математичес ких теориях, всем им присущи два общих свойства. Одно из них - использовани е избыточности. Закодированные цифровые сообщения всегда содержат доп олнительные, или избыточные, символы. Эти символы используют для того, чт обы подчеркнуть индивидуальность каждого сообщения. Их всегда выбираю т так, чтобы сделать маловероятной потерю сообщением его индив и дуальности из-за искажения при воздействии помех достаточно большого числа символов. Второе свойство состоит в усреднении шума. Эффект у с реднения достигается за счет того, что избыточные символы зав исят от н е скольких информ ационных символов. Для понимания процесса кодирования полезно рассмот реть каждое из этих свойств отдельно. Рассмотрим вначале двоичный канал связи с помехами, приводящими к тому, что ошибки появляются независимо в каждом символе и средняя в е роятность ошибки равна Р=0,01. Если тре буется рассмотреть произвольный блок из 10 символов на выходе канала, то в есьма трудно выявить символы, которые являются ошибочными. Вместе с тем если сч и тать, что такой бл ок содержит не более трех ошибок, то мы будем неправы лишь два раза на ми л лион блоков. Кроме того, в ероятность, что мы окажемся правы, возрастает с ув е личением длины блока. При увеличен ии длины блока доля ошибочных символов в блоке стремится к средней часто те ошибок в канале, а также, что очень важно, доля бл о ков, число ошибок в которых существ енно отличается от этого среднего значения, стан о вится очень малой. Простые вычисле ния помогают понять, насколько верным является это у т верждение. Рассмотрев, например, то т же канал, вычислим вероятность того, что доля ошибочных символов превы шает значение p, и построим график этой функции для н е скольких значений длины блока. Рис. 1. Вероятность того, что доля ошибочных символо в e/N в блоке длиной N превышает р при вероя т ности Р e =0,01 Кривые на рис.1 показывают, что при обработке символ ов блоками, а не одного за другим можно уменьшить общую частоту ошибок. Пр и этом потребуется, чтобы существ о вала схема кодирования, нечувствительная к ошибкам в некотор ой доле символов блока и не приводящая при этом к потере сообщением свое й индивидуальности, т. е. не приводящая к ошибочн о му блоку. Из графиков для различных длин блоков ви дно, какую именно долю ошибок нужно исправлять, чтобы получить заданную вероя т ность ошибки блока . Он показывает также, что при фиксированной вероя т ности ошибки блока доля ошибок, кот орые нужно исправлять, уменьшается при возрастании длины блока. Сказанн ое свидетельствует о резервах улу ч шения характеристик при усреднении шума и о том, что эти резер вы возра с тают при увеличе нии длины блока. Таким образом, длинные блоковые коды эффективнее коротк их. После того как установлена целесообразность и с правления ошибок в символах, возни кает следующий логичный вопрос: как это сделать? Ключ лежит в избыточнос ти. После некоторых размышлений читатель поймет, что при исправлении оши бок в сообщении, представля е мом последовательностью из n двоичных символов, очень важно у честь, чтобы не все 2 n возможн ых последовательн о стей п редставляли сообщения. В самом деле, когда каждая из возможных принятых п о следовательностей n сим волов представляет некоторое сообщение, нет никаких оснований сч и тать, что одна последователь ность является более правильной, чем любая другая. Пр о должая рассуждать таким же способо м, можно ясно увидеть, что для исправления всех наборов из t или менее ошиб ок необходимо и дост а точн о, чтобы каждая последовательность, представляющая сообщение, отличала сь от последовательности, предста в ляющей любое другое сообщение, не менее чем в 2t+1 местах. Наприме р, для исправл е ния всех од иночных или всех двойных ошибок в символах нужно, чтобы каждые две после довател ь ности, представл яющие разные сообщения, отличались не менее чем в пяти символах. Каждая п ринятая последовательность, содержащая два ошибо ч ных символа и, следовательно, отлич ающаяся от посланной последовател ь ности ровно в двух местах, будет всегда отличаться от всех дру гих послед о вательностей, представляющих сообщения, не менее чем в трех местах. Чи с ло позиций, в которых две последова тельности отличаются друг от друга, будем называть расстоянием Хемминг а d между этими двумя последов а тельностями. Наименьшее значение d для всех пар кодовых после довательностей наз ы вает ся кодовым расстоянием и обозначается d min . Поскольку d min в сегда должно быть на единицу больше удвоенного числа исправляемых ошиб ок, можно написать t=[(d min -l)/2], где [ ] о бозначает целую часть. Параметр t указывает, что все комбинации из t или ме нее ошибок в любой принятой последовательности могут быть исправлены.И меются модели к а налов, в к оторых значение t может быть больше указанного. Пример. Рассмотрим код, состо ящий из четырех кодовых слов 00000, 00111,11100 и 11011. Каждое кодовое слово используется для представления одного из четырех возможных сообщении. Поскольку код вкл ю чает лишь небольшую д олю всех 32 возможных последовательностей из пяти симв о лов, мы можем выбрать кодовые слова таким образом, чтобы каждые два из них отличались друг от друга не менее ч ем в трех поз и циях. Таким о бразом, кодовое расстояние равно трем и код может исправлять одиночную о шибку в любой позиции. Чтобы провести процедуру декодирования при этом к оде, каждой из 28 недопустимых последовательностей нужно поставить в соо т ветствие ближайшую к ней допустимую последовательность. Этот процесс ведет к созданию таблицы д екодирования, которая строится следующим о б разом. Вначале под каждым кодовым словом выписывае м все возможные последовательности, отличающиеся от него в одной позици и. В результате получаем часть табл. 1, заключенную между штриховыми линия ми. Зам е тим, что после пост роения этой части осталось воcемь последовательностей. Каждая из этих по следовательностей отличается от каждого кодового слова не менее чем в д вух позициях. Однако в отличие от других последовательн о стей эти восемь последовательност ей нельзя однозначно разместить в таблице. Напр и мер, последовательностью можно пом естить либо в первый, либо в четвертый столбец. При использовании этой та блицы в процессе декодир о вания нужно найти столбец, в котором содержится принятая последовател ь ность, и а качестве выходн ой последовательности декодера взять кодовое слово, находящееся в вер х ней строке этого столбца. Таблица 1. Таблица декодирования для кода с четырьмя словами 00000 10000 01000 00100 00010 00001 11100 01100 10100 11000 11110 11101 00111 10111 01111 00011 00101 00110 11011 01011 10011 11111 11001 11010 10001 10010 01101 01110 10110 10101 01010 01001 Причина, по которой таблица декодирования должна строиться име н но таким о б разом, очень проста. Вероятность появления фиксир ованной комбинации из i ошибок равна Р t e (1 -Р e ) 5-i Заметим что при Р e<1/2 (1 -Р e ) 5 P e (1 -Р e ) 4 Р e 2 (1 -Р e ) 3 ... Таким образом, появление фиксированной одиночной ошибки более вероятн о, чем фиксированной комбинации двух ошибок, и т. д. Это значит, что декодер, который дек о дирует кажду ю принятую последовательность в ближайшее к ней по расстоянию Хемминга кодовое слово, выбирает в де й ствительности то кодовое слово, вероятность передачи которо го максимал ь на (в предпол ожении, что все кодовые слова равновероятны). Декодер, ре а лизующий это правило декодировани я, является декодером максимального правдоподобия, и в указанных предпо ложениях он минимизирует вероя т ность появления ошибки декодирования принятой последовател ьности. В этом смысле такой декодер является оптимальным. Это понятие оч ень важно, поскольку декодеры максимального правдопод о бия часто используются для коротки х кодов. Кроме того, параметры декодера максимального пра в доподобия могут служить эталоном, с которым сравниваются пар а метры других, неоптимальных декодеров. Если декодирование ве дется с помощью таблицы декодирования, то элементы таблицы можно распол ожить так, чт о бы получить декодирование по максимуму правдоподобия. К сожалению, объем таблицы ра стет экспоненциально с ростом длины блока, так что и с пользование таблицы декодировани я для дли н ных кодов нецел есообразно. Однако таблица декодирования часто оказывается полезной д ля выя с нения важных свойс тв блоковых кодов. Множество кодовых слов в таблице декодирования является подмн о жеством (первой строкой таблицы декодирования) множества всех 2 n посл е дователь ностей длиной n. В процессе построения таблицы декодирования множество в сех последовательностей длиной n разбивается на непересекающиеся подм ножества (столбцы таблицы декодиров а ния). В случае когда код исправляет t ошибок, число N e последовательностей длиной n в каж дом подмножестве удовлетворяет неравенству N e >=1+n+C n 2 +...+C n t , (2) где C n i - i-й биномиальный коэффициент. Неравенство (2) следует непосредственно из того, что имеется ровно n различ ных последовательностей, отличающихся от данной последовател ь ности в одной позиции, C n 2 последоват ельностей, отличающихся в двух п о зициях, и т. д. Как и в приведенном выше простом примере, после ра змещ е ния всех последоват ельностей, отличающихся от кодовых в t или менее п о зициях, почти всегда остаются нера змещенные последов а тель ности [отсюда неравенство в (2)]. Теперь можно связать избыточность кода c чи с лом ошибок, которые им ис правляются Заметим сначала, что число всех возможных последовательн о стей равно 2 n . Каждый столбец таблицы декодировани я содержит N e таких последова тельностей, поэтому общее число кодовых слов должно удовлетворять нер а венству N e <=<2 n /(1+n+C n 2 +...+C n t ), (3) Это неравенство называется границей Хемминга или границей сферической уп а ковки. Равенство в (3) до стигается только для так называемых совершенных кодов. Эти коды исправл яют все наборы из t или менее ош и бок и не исправляют никаких других наборов. Число известных с оверше н ных кодов очень не велико, так что равенство в (1.3) достигается в очень ре д ких случаях. Процесс кодирования состоит в том, что наборы k информационных символов отображ а ются в кодовые по следовательности, состоящие из n символов. Любое такое отображение будем называть (n, k)-кодом, хотя обычно такое название применяется только к линей ным кодам (которые обсуждаются позже). Поскольку число последовательнос тей длиной k равно 2 k , неравенс т во (3) можно переписать сле дующим образом: 2 k <=2 n /(1+n+C n 2 +...+C n t ), (4) Мера эффективности кода определяется отношением R=k/n (5) и называется скоростью кода. Доля избыточно передаваемых символов равн а 1-R. Отображение, возникающее при кодировании, можно задавать таблицей к о дирования. Например, код с че тырьмя кодовыми словами задается табл. 2. Таблица 2. Таблица поиска при декодировании Входная последовательность Кодовая последовательность 00 01 10 11 00100 01111 11011 10000 Часть кодовой последовательности, заключенная ме жду штриховыми линиями, совпадает с входной последовательностью. Поэто му каждой код о вой последо вательности, легко однозначно сопоставить входную последов а тельность. Не все блоковые коды обл адают этим свойством. Те, которые им обладают, называются систематически ми кодами. Понятие избыточных си м волов для систематических кодов становится абсолютно ясным, и избыто ч ными символами в табл. 1 являются символы на позициях 1, 4 и 5. Коды, не о б ладающие указанным свойством, назы ваются несистематическими. Существует много хороших конструктивных методов кодирования, позв о ляющих исправлять кратные о шибки и приводящих к заметному уменьш е нию частоты появления ошибочных символов. Эти коды легко с троятся и с помощью современных полупрово д никовых устройств относительно просто декодируют ся. Например, существует блоковый код длиной 40, содержащий 50% избыточных си мволов и позволяющий исправлять чет ы ре случайные ошибки. На рис. 1 показано, что при Р e =0,01 этот код имеет вероятность ошибки бл ока, меньшую 10 -4 . Если этого нед остаточно, разработчик увел и чивает избыточность, чтобы исправлять большее число ошибок, и ли перех о дит к кодам с бол ьшей длиной блока и получает выигрыш за счет большего усреднения. В кажд ом случае нужно принимать во внимание возникающие дополнительные затр аты. Однако обе указанные возможности допустимы и могут представлять пр актически приемлемые альтернативы. Прежде чем и д ти дальше, сделаем небольшое отсту пление, которое не имеет большого практического значения, но привлекает внимание специалистов по теории кодирования в течение многих лет. Форма кривых, изображенных на рис. 1, позволяет предположить, что если имеется сх ема, исправляющая фикс и ро ванную долю t/n ошибочных символов в блоке (в нашем случае t/n незн а чительно превышает 0,01), то, выбирая дл ину блока достаточно большой, можно сделать долю ошибок сколь угодно мал ой. К сожалению, это оказ ы в ается очень трудной задачей. Большинство конструктивных процедур м о жет обеспечить постоянное о тношение t/n лишь при возрастающей доле и з быточных символов (другими словами, R->0 при n->oo). Таким образом, п о теря эффективности воз никает из-за того, что доля полезных сообщений становится очень малой пр и большой длине блока. Частично эта задача была решена Юстесеном в 1972 г. Юстесен показал, что можно п о строить класс асимптотичес ки хороших (в указанном здесь смысле) кодов и указать для них процедуру де кодирования. Однако, насколько известно, эти коды не применялись ни в одн ой из существующих систем связи. Основные параметры помехоустой чивых кодов Проблема повышения верности обусловлена не соотве тствием между требовани я ми, предъявляемыми при передачи данных и качеством реальных каналов свя зи. В сетях п е редачи данны х требуется обеспечить верность не хуже 10 -6 - 10 -9 , а при испол ьзовании реальных каналов связи и простого (первичного) кода указанная в ерность не превышает 10 -2 - 10 -5 . Одним из путей решения задачи повышения верности в настоящее время явля ется использование специальных процедур, основанных на применении пом ехоустойч и вых (корректир ующих) кодов. Простые коды характеризуются тем, что для передачи информации использу ются все к о довые слова (ко мбинации), количество которых равно N=q n (q - основание кода, а n - длина кода). В общем случае они могут отл и чаться друг от друга одни м символом (элементом). Поэтому даже один ошибочно принятый символ приво дит к замене одного к о дов ого слова другим и, следовательно, к неправильному приему сообщения в це лом. Помехоустойчивыми называются коды, позволяющие обнаруживать и (и ли) исправлять ошибки в кодовых словах, которые возникают при передаче п о каналам связи. Эти коды строятся таким образом, что для передачи сообщ е ния используется лишь ча сть кодовых слов, которые отличаются друг от друга более чем в одном симв оле. Эти кодовые слова называются разреше н ными. Все остальные кодовые слова не используются и отн осятся к числу запрещенных. Применение помехоустойчивых кодов для повышения верности передачи дан ных связа н но с решением з адач кодирования и декодирования. Задача кодирования заключается в получении при передаче для ка ж дой k - элементной комбинации из м ножества q k соответствующег о ей код о вого слова длино ю n из множес т ва q n . Задача декодирования состоит в получении k - элементной комбин а ции из принятого n - разрядного кодов ого слова при одновременном обн а ружении или исправлении ошибок. Основные параметры помехоустойчивых кодов: Длина кода - n; Длина информационной последовательности - k; Длина проверочной последовательности - r=n-k; Кодовое расстояние кода - d 0 ; Скорость кода - R=k/n; Избыточность кода - Rя; Вероятность обнаружения ошибки (искажения) - Р ОО ; Вероятность не обнаружения ошибки (искажения) - Р НО . Кодовое расстояние между двумя кодовыми словами (р асстояние Хэмминга) - это число позиций, в которых они отличаются друг от д руга. Кодовое расстояние кода - это наименьшее расстояни е Хэмминга между различными п а рами кодовых слов. Основные зависимости между кратностью обнаружива емых ошибок t 0 , и с правляемых ошибок t u , исправлением стираний t c и кодовым расстоянием d 0 кода: Стиранием называется "потеря" значения передаваем ого символа в некот о рой п озиции кодового слова, которая известна. Код, в котором каждое кодовое слово начинается с информационных символо в и заканчивается проверочными символами, называется систематич е ским. Граничные соотношения между параметрами помехоу стойчивых кодов Одной из важнейших задач построения помехоустойч ивых кодов с заданными х а рактеристиками является установление соотношения между его способнос тью обнаруж и вать или испр авлять ошибки и избыточностью. Существуют граничные оценки, связывающие d 0 , n и k. Граница Хэмминга, которая близка к оптимальной для высоко скоростных ко дов, опред е ляется соотнош ениями: для q-ного кода для двоичного кода Граница Плоткина, которую целесообразно использо вать для низкоскоростных кодов о п ределяется соотношениями: для q-ного кода для двоичного кода Границы Хэмминга и Плоткина являются верхними границами для кодового р асстояния при заданных n и k, задающими минимальную избыто ч ность, при которой существует поме хоустойчивый код, имеющий мин и мальное кодовое расстояние и гарантийно исправляющий t u - кратные оши б ки. Граница Варшамова-Гильберта (нижняя граница), определяемая соотнош е ниями: и показывает, при каком значении n-k определено сущест вует код, гарантийно исправля ю щий ошибки кратности t u . ЛИТЕРАТУРА 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