Какими помехозащитными свойствами обладает инверсный код
КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Помехозащищенные коды
Лекция № 5
Помехозащищенными, или корректирующими, кодами называются коды, позволяющие обнаружить или обнаружить и исправить ошибки в кодовых комбинациях. Отсюда и деление этих кодов на две группы: коды с обнаружением ошибок и коды с обнаружением и исправлением ошибок.
Принципы обнаружения и исправления ошибок кодами хорошо иллюстрируются при помощи геометрических моделей. Любой n-элементный двоичный код можно представить с помощью n-мерного куба, в котором каждая вершина отображает кодовую комбинацию, а длина ребра куба соответствует одной единице. В таком кубе расстояния между вершинами (кодовыми комбинациями) измеряется минимальным количеством ребер, находящихся между ними, обозначается буквой d и называется кодовым расстоянием.
Таким образом, кодовое расстояние– это то минимальное число элементов, в которых одна кодовая комбинация отличается от другой.
При n=1 n–мерный куб превращается в прямую длиной d=1, на одном конце которой располагается 1, а на другом 0. (n – число разрядов)
При n=2 имеем четыре возможные комбинации (N= 22 =4), которые располагаются на четырех вершинах квадрата. При этом комбинации 00 и 11, а также 10 и 01 отличаются друг от друга в двух разрядах, т.е. d =2.
Кодовое расстояние между двумя комбинациями двоичного кода равно числу единиц, полученных при сложении этих комбинаций по модулю 2, например, 10 01 = 11 и 00 11 = 11. Такое определение кодового расстояния удобно при большой разрядности кодов. Так, складывая комбинации 10110101101
10000000010
мы определяем, что расстояние между ними d=7.
Для кода с n=3 восемь кодовых комбинаций размещаются на вершинах трехмерного куба. Этот куб строится так, что одна из его вершин лежит в начале координат. Каждой вершине куба приписывается кодовая комбинация по следующему правилу: на i-ом месте кодовой комбинации ставится 0, если проекция этой вершины на i-ую ось координат равна 0, и 1, если проекция равна 1. Например, мы хотим узнать, какую следует записать комбинацию в вершине А6. Проектируя эту вершину на ось X1 , мы получим единицу.
На втором месте комбинации запишется также 1 (проекция на ось X2 равна единице). Т.к. проекция на ось X3 равна нулю (проекция в начале координат), то на третьем месте комбинации запишется 0. Вся комбинация в точке А6 – 110. Если использовать все восемь слов, то образуется двоичный код на все сочетания. Как было показано выше, такой код непомехоустойчив. Если же уменьшить число используемых комбинаций с 8 до 4,то появится возможность обнаружения одиночных ошибок. Для этого выберем только такие комбинации, которые отстоят друг от друга на расстоянии d=2, например, А0 А6 А3 А5
000 110 011 101
Если будет принята комбинация 100, отстоящая от комбинации 000, 110 и 101 на расстоянии d=1, то очевидно, что при приеме такой комбинации произошла одиночная ошибка.
Представленные комбинации построены по определенному правилу, а именно содержат четное число единиц, а принятая комбинация 100-нечетное. Можно утверждать, что комбинация 100 образовалась при искажении одного разряда одной из разрешенных комбинаций, но определить, какая именно комбинация искажена, невозможно. Поэтому такие коды называются кодами с обнаружением ошибок.
Кроме указанной выше группы комбинаций, в кубе можно найти еще одну группу комбинаций с кодовым расстоянием d=2 А7 А1 А2 А4
(111 001 010 100)
В этих кодовых комбинациях нечетное число единиц и каждая из них может быть использована для обнаружения ошибки, возникшей при передаче, т.к. при одиночном искажении в комбинации будет четное число единиц. Однако если мы хотим получить код с обнаружением одиночной ошибки , то в передаче в передаче может участвовать только одна группа ,т.е. четыре комбинации из возможных 8. В противном случае мы придем к непомехоустойчивому коду, в котором будут встречаться комбинации с d=1.
Таким образом, в помехозащищенных кодах есть комбинации разрешенные, составленные по определенному правилу и есть комбинации запрещенные, не соответствующие этому правилу. Так, если из восьми комбинаций трехразрядного кода мы образовали четыре комбинации, позволяющие обнаруживать одиночную ошибку (например, 111, 001, 010 и 100), то эти комбинации будут разрешенными, а остальные четыре ( 000, 011, 101, 110) являются запрещенными и должны фиксироваться на приеме как искаженные. Иногда совокупность разрешенных кодовых комбинаций, которые при заданных возможных искажениях не могут перейти друг в друга, называют системой непереходящих друг в друга сигналов.
Построение помехоустойчивого кода связано с недоиспользованием кодовых комбинаций, приводящим к так называемой избыточности. Избыточность означает, что из исходных символов можно построить больше комбинаций, чем их используется в данном коде. Если еще больше ограничить число разрешенных комбинаций, то можно создать код и с исправлением ошибок.
Выберем в трехмерном кубе такие вершины, кодовые обозначения которых отличались бы друг от друга на d=3. Такие вершины расположены на концах пространственных диагоналей куба. Их может быть только четыре пары: 000 и 111 или 001 и 110, или 100 и 011, или 010 и 101. Однако из этих четырех пар для передачи можно использовать только одну любую пару, т.к. использование большего числа пар приведет к тому, что в передаче будут использоваться комбинации, отличающиеся друг от друга на d<3.
Код, образованный по такому правилу и состоящий в данном случае из двух комбинаций, может исправить одиночную ошибку или обнаруживать две ошибки без возможности их исправления.
Пусть, например, передается код, состоящий из слов 001 и 110. На приеме получена комбинация 100. Сравнение ее с исходными комбинациями показывает, что от комбинации 110 она отличается в одном (втором) разряде, а от комбинации 001 в двух разрядах. Если считать, что сделана одна ошибка, то полученную комбинацию 100 следует исправить на 110.
От разрешенной комбинации 001 отличаются на d=1 комбинации 011, 000 и 101, а от комбинации 110 – комбинации 111,100 и 010. Они и являются своего рода комбинациями – спутниками, которые после приема можно относить к той или иной исходной комбинации.
Когда мы говорим об исправлении одиночной ошибки, то считаем, что вероятность двойной ошибки в канале связи пренебрежимо мала. Если такая вероятность достаточно велика, то код с d=3 можно использовать для обнаружения двойных ошибок, но при этом он уже исправлять одиночную ошибку не может. Действительно, если в нашем примере была принята комбинация 100,то уже нельзя утверждать, что была передана комбинация 110, т.к. при двойных ошибках это могла быть и искаженная комбинация 001.
Таким образом, дальнейшее повышение помехоустойчивости кода связано с увеличением кодового расстояния d, а это приводит к увеличению избыточности (вместо восьми комбинаций в нашем примере используются уже только две).
Корректирующая способность кода тесно связана с кодовым расстоянием:
а) при d =1 ошибка не обнаруживается;
б) при d =2 обнаруживаются одиночные ошибки;
в) при d =3 исправляются одиночные ошибки или обнаруживаются двойные.
В общем случае d=r+s+1, (3-5)
где d – минимальное кодовое расстояние;
r – число обнаруживаемых ошибок в слове;
s – числоисправляемых ошибок в слове.
При этом обязательным условием является . Если r=s, то код обнаруживает 2x или исправляет x ошибок. Так в нашем примере d=3, и если r=s=1, то код может обнаружить одну ошибку и исправить ее, т.е. x=1. Если r=2, s=0, то код может обнаружить только две ошибки. Как следует из уравнения (3-5), для того чтобы код мог исправить одну ошибку и обнаружить две, необходимо, чтобы d=2+1+1=4. При том же d=4 может быть и вариант, когда r=3, s=0. Если d=5, то могут быть уже три варианта: r= s=2; r=3, s=1; r=4, s=0.
Если код только обнаруживает ошибки, то d=r+1, т.е. r=d — 1 (3-6)
Если код только исправляет ошибки, то d=2s+1, т.е. (3-7)
Итак, использование геометрических моделей позволяет просто строить малоразрядные корректирующие коды. Однако при длине кода n > 3 трудно уже воспользоваться геометрической моделью, т.к. такая модель должна быть многомерной. Если еще для n=4 можно вычертить четырехмерный “куб”, так называемый гиперкуб, то для n >4 это практически сделать невозможно. Поэтому для построения многоразрядных помехоустойчивых кодов используются различные правила и методики, к рассмотрению которых мы и перейдем.
Дата добавления: 2014-01-07; Просмотров: 1799; Нарушение авторских прав?
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Рекомендуемые страницы:
Читайте также:
Лекция 5. Кодирование
и декодирование дискретных сообщений
План лекции
— Основные понятия и определения в области
кодирования сообщений
— Условная классификация кодов
— Системы счисления и методики построения
кодов
— Запись кодовых комбинаций в виде многочлена
— Непомехозащищенные коды, основные понятия
— Помехозащищенные коды, основные понятия
Основные понятия и определения в области кодирования
сообщений
После того как непрерывное сообщение с помощью квантования
преобразовано в дискретное сообщение, его необходимо передать по каналу связи.
При этом передача должна осуществляться без искажений или с минимальными искажениями.
Кодирование — преобразование дискретного сообщения в дискретный
сигнал, осуществляемое по определенному правилу. Обратный процесс — декодирование
— это восстановление дискретного сообщения по сигналу на выходе дискретного
канала, осуществляемое с учетом правила кодирования [34].
Код — совокупность условных сигналов, обозначающих дискретные
сообщения. Код это правило, по которому записываются различные кодовые слова
или числа. Понятие кода является чисто математическим. Любой код должен удовлетворять
главному требованию — однозначности соответствия между сообщением и кодовым
словом, в противном случае окажется невозможным расшифровать сообщение на
приемной стороне. В системах передачи сообщений кодовые слова, или кодовые
комбинации, преобразуются в сигналы, передаваемые по каналу связи. При этом
каждому символу кода должен соответствовать свой, и только свой, элементарный
сигнал.
Оглавление
Условная классификация кодов
Все используемые в системах передачи информации коды можно
условно разделить по следующим признакам:
1. По числу используемых элементарных символов:
— двоичные (кодовые слова состоят из символов 0, 1);
— троичные (кодовые слова состоят из символов 0, 1,2);
— К-ичные (кодовые слова состоят из символов 0, 1,…,
К);
2. По числу элементарных символов в каждом слове, или кодовой
комбинации (по общему числу символов):
— равномерные; в таких кодах все кодовые слова
содержат одно и то же постоянное число элементов,
то есть n = const;
— неравномерные; разные сообщения в этих кодах кодируются
словами разной длины, то есть n = var,
3. По способности обнаруживать и/или исправлять ошибки:
— непомехоустойчивые (непомехозащищенные, неизбыточные)
— коды, неспособные не только исправлять, но даже обнаруживать ошибки;
— помехоустойчивые (помехозащищенные) — коды, способные
обнаруживать и/или исправлять ошибки различных типов (избыточные коды);
4. По разделимости информационных и избыточных элементов:
— систематические, в которых есть четкое различение между
информационными и избыточными элементами; особенно удобны коды, в которых
информационные элементы занимают первые т позиций, а за ними следуют избыточные
элементы на k позициях,
— несистематические, в которых нельзя различить информационные
и избыточные элементы.
Оглавление
Системы счисленияи и методики построения кодов
Установлено, надежность передачи значительно увеличивается
при уменьшении числа и усилении различия признаков. В настоящее время наиболее
часто применяют двоичные коды.
Методика построения кодов тесно связана с соответствующими
системами счисления. Рассмотрим кратко двоичную систему исчисления, поскольку
возникшие на ее основе двоичные коды получили наиболее широкое распространение
в системах передачи информации.
Построение любой системы счисления начинается с выбора
ее основания, т. е. того количества цифр, из комбинаций которых можно получить
любое число. В основу двоичной системы положены лишь два числа: 0 и 1. Десятичное
число 2 передается как 10
Двоичная система счисления нашла широкое применение в вычислительной
технике, где за счет применения в ней только двух цифр (0 и 1) легко осуществляются
арифметические операции. Схемная реализация операции с двоичными числами проста.
Это объясняется тем, что многие устройства, используемые в вычислительной
технике и телемеханике, являются устройствами релейного действия (электромеханические
реле, триггеры, лампы тлеющего разряда, магнитные элементы с прямоугольной
петлей гистерезиса и др.), т.е. обладают двумя устойчивыми состояниями, соответствующими
1 или 0.
Перевод десятичного числа в двоичное и обратно. Для этого
следует воспользоваться общими правилами перевода из одной системы счисления
в другую, т. е. поделить исходное число на основание второй системы счисления,
а затем частное от деления снова поделить на то же основание до получения
в частном единицы. Остатки при каждом акте деления образуют число в новой
системе счисления.
Для перевода двоичного числа в десятичное нужно удваивать
числа начиная со старшего разряда, придерживаясь следующих правил:
1) если в следующем разряде стоит нуль, то число только
удваивается;
2) если в следующем разряде стоит единица, то число удваивается
и к нему прибавляется еще единица.
Для примера переведем в десятичный эквивалент двоичное
число 11101. Первую единицу удвоим и, прибавив к результату 1, получим 3.
Далее удвоим 3 и, прибавив 1, получим 7. Удвоив 7, получим 14. И наконец,
удвоив 14 и прибавив 1, получим 29, т. е.
Перевод можно получить также путем подписывания под двоичным
числом его десятичного эквивалента. Далее производят суммирование всех разрядов
в десятичном эквиваленте, в которых стоит единица. Например, двоичное число
в десятичном эквиваленте равно 53.
Оглавление
Запись кодовых комбинаций в виде многочлена
Любое число в системе счисления с основанием X можно представить
в виде многочлена. Так, n-разрядное число запишется в виде
где а — цифровые знаки, имеющие значения от 0 до (Х – 1).
В десятичной системе счисления Х=10, а — это цифры 0, 1,
2, …, 9.
Например, четырехзначное число 4357 запишется как:
В двоичной системе счисления, где Х=2, коэффициенты а принимают
только одно из двух значений: 1 или 0. Двоичное число 10101001 в десятичном
эквиваленте запишется таким образом:
или в виде многочлена
Опуская члены с коэффициентами, равными нулю, и не выписывая
единицы, как множитель, получаем
Таким образом, члены многочленов записываются только при
наличии коэффициента единицы. При этом степень соответствующего числа многочлена
берется уменьшенной на единицу по отношению к номеру разряда в двоичной записи,
отсчитанному справа налево. Так, первым записывается X7, несмотря на то, что
этот член в двоичной записи находится в восьмом разряде.
Оглавление
Непомехозащищенные коды, основные понятия
Особенностью непомехозащищенных кодов является наличие
в их составе кодовых комбинаций, которые отличаются друг от друга лишь в одном
разряде. Типичным кодом такого типа является двоичный код. к примеру, комбинации
0010 и 0011 отличаются друг от друга лишь в младшем разряде. Если помеха исказит
первую комбинацию, то будет принят сигнал 0011 и будет неясно, то ли принята
первая искаженная комбинация, то ли вторая неискаженная. Можно найти еще ряд
комбинаций в том же коде, которые отличаются друг от друга только в одном
разряде. Например, комбинации 0101 и 0111 отличаются во втором разряде, комбинации
0011 и 0111 — в третьем разряде, а комбинации 1110 и 0110 — в четвертом разряде.
В целом это делает двоичный код на все сочетания непомехозащищенным.
Таким образом, непомехоустойчивыми (или непомехозащищенными)
кодами называют коды, в которых искажение одного разряда кодовой комбинации
не может быть обнаружено. Иногда их называют обыкновенными кодами.
Оглавление
Помехозащищенные коды, основные понятия
Помехозащищенными (или корректирующими) называются коды,
позволяющие обнаружить и исправить ошибки в кодовых комбинациях. Отсюда и
деление этих кодов на две большие группы:
1) коды с обнаружением ошибок;
2) коды с обнаружением и исправлением ошибок.
В помехозащищенных кодах есть комбинации разрешенные, составленные
по определенному правилу, и запрещенные, не соответствуюшие этому правилу.
Фиксирование запрещенных комбинации на приемной стороне означает искажение
сигнала (помехи).
Построение помехоустойчивого кода (а код с обнаружением
ошибки является простейшим типом такого кода) связано с недоиспользованием
кодовых комбинаций, приводящим к так называемой избыточности. Избыточность
означает, что из исходных символов можно построить больше комбинаций, чем
их применено в данном коде. Уменьшение числа используемых комбинаций приводит
к повышению помехоустойчивости кода.
Аналогичным образом осуществляется построение кодов с обнаружением
и исправлением ошибок (в них число разрешенных комбинаций ограничено еще сильней,
а избыточность выражена в большей степени).
Оглавление
Рекомендуемая литература
1. Тутевич В.Н. Телемеханика, — 2 –е изд.- М.: Высш. шк.,
19985. – 423 с.
2. Цымбал В.П. Задачник по теории информации и кодированию.
К.: Вища школа, 1976. – 276 с.
3. Питерсон У., Уэлдон Э. Коды исправляющие ошибки. – М.:
Мир, 1976.
Контрольные задания для СРС
1. Для чего при передаче информацию кодируют?
2. По каким признакам можно разделить коды в системах передачи
информации?
3. Построение кода Хэмминга.
4. Виды помехозащищенных и корректирующих кодов.
5. Перевод десятичных чисел в двоичные и обратно.
6. Операции над кодовыми комбинациями, записанными в виде
многочленов (сложение, умножение, деление).
7. Недвоичные и частотные коды.
Оглавление
К лекции №4… ______________________________________________________________________________________
К лекции №6…
К СОДЕРЖАНИЮ УЧЕБНИКА …