Помехоустойчивое кодирование - раздел Математика, ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ Пусть Имеется Канал Связи C, Содержащий Источник Помех:
...
Пусть имеется канал связи C, содержащий источник помех:
,
где S – множество переданных, а – соответствующее множество принятых по каналу сообщений. Кодирование F, обладающее таким свойством, что
,
называется помехоустойчивым.
Если A=B={0,1}, то ошибки в канале могут быть следующих типов:
· 01, 10 – ошибка типа замещения разряда;
· 0, 1– ошибка типа выпадения разряда;
· 1, 0 – ошибка типа вставки разряда.
Пусть – множество слов, которые могут быть получены из слова s в результате всех возможных комбинаций допустимых в канале ошибок , то есть , . Если , то та конкретная последовательность ошибок, которая позволяет получить из слова s слово , обозначается . Если тип возможных ошибок в канале подразумевается, то индекс не указывается.
Теорема 9.3.Чтобы существовало помехоустойчивое кодирование с исправлением всех ошибок, необходимо и достаточно, чтобы , то есть необходимо и достаточно, чтобы существовало разбиение множества B* на множества , такое что .
Доказательство. Если кодирование помехоустойчивое, то очевидно, что . Обратно: по разбиению строится функция .
Рассмотрим множество из всех двоичных последовательностей (векторов), имеющих вид
.
Введем в множестве операцию сложения +, определив для последовательностей и их сумму с помощью соотношения: , где – это сумма по модулю два.
Расстояние Хэммингамежду кодовыми словами определяется как число позиций таких, что . При построении вектора пары одинаковых двоичных символов будут давать 0 , а пары различных двоичных символов будут давать 1.
Поэтому расстояние Хэмминга можно определить как число компонент вектора , которые равны 1.
Введенное таким образом расстояние Хэмминга удовлетворяет следующим условиям:
·
· ;
· – «неравенство треугольника».
В общем случае расстоянием называют функцию, удовлетворяющую вышеприведенным условиям. Этим условиям, в частности, удовлетворяет геометрическое расстояние между двумя точками () и () на плоскости: .
При наличии бит можно построить кодовых слов. Однако часто нужны не все из этих слов. Если использовать только часть кодовых слов, то с помощью проверок на четность и других приемов можно обнаружить ошибки и даже их исправлять.
Предположим, что из используются только слов: . Если эти слова таковы, что при всех :
, (7.1)
то можно исправлять любые ошибки кратности .
Допустим, что в некоторых компонентах слова при передаче возникли ошибки, в результате которых символы 0 были приняты как 1, а символы 1 – как 0 (ошибки типа замещения). Получившееся в результате слово находится на расстоянии от слова . Следовательно, если считать, что ошибки при передаче могут возникать не более чем в компонентах, то совокупность всех слов, которые могут получиться из , представляет собой множество .
Из неравенства треугольника и условия (7.1) следует , если только . Действительно, допустим, что существует слово . Тогда и .
Согласно неравенству треугольника
,
что приводит к противоречию с условием (9.1).
Множество называется областью декодирования для слова . Так как области декодирования не пересекаются, то при приеме слова из области декодирования можно считать, что передавалось слово . Если при этом число ошибок не превосходит , то при приеме всегда будет приниматься правильное решение.
Так как число элементов в множестве равно числу способов выбора некоторых () компонент слова , то
.
Далее, так как , то: , то есть
. (9.2)
Неравенство (9.2) называется границей Хэмминга. Оно дает оценку сверху для числа кодовых слов, которые можно использовать для передачи, если их длина равна бит и нужно исправлять все -кратные ошибки.
Пример 9.5.Пусть =8, тогда . Поскольку , то ; ; ; ; .
Если =4, то .
Если =3, то .
Если =2, то .
Если =1, то .
Если =0, то .
Таким образом, если встречаются только одиночные ошибки типа замещения, то при использовании 8 бит можно безошибочно передавать 28 слов. В общем случае, если имеется бит и нужно исправлять одиночные ошибки типа замещения, то граница Хэмминга определяется следующим выражением, являющимся частным случаем формулы (9.2):
. (9.3)
Обозначим минимальное число бит, необходимое для передачи слов, буквой . Тогда:, и из формулы (9.3) следует
. (9.4)
Таким образом, для помехоустойчивого кодирования сигналов при одиночных ошибках типа замещения необходимо использовать дополнительные бит, количество которых должно удовлетворять условию (9.4). Рассматриваемый случай простейший, но одновременно практически очень важный. Таким свойством, как правило, обладают внутренние шины передачи данных в современных компьютерах.
Пример 9.6.Для сообщения длиной потребуется дополнительных разрядов, поскольку 64=.
Код, в котором используются дополнительные разряды для помехоустойчивой передачи сигналов, называется кодом Хэмминга.
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Помехоустойчивое кодирование
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Счетные и несчетные числовые множества
Теория множеств появилась в конце 19 века благодаря работам немецкого математика Георга Кантора (1845-1918). Понятие множества принадлежит к числу фундаментальных неопределяемых понятий математики.
Позиционные и непозиционные системы
Системой счисления называется метод записи чисел в виде комбинаций графических символов. Число – это некоторая абстрактная сущность для описания количества, а цифры – знаки, ис
Десятичная система
Существуют различные позиционные системы исчисления, отличающиеся между собой количеством используемых знаков. Чтобы различать числа в разных системах исчисления, в конце числа ставят индекс – симв
Двоичная система
Двоичная (бинарная) система счисления является самой простой из всех позиционных систем. Она содержит только два символа 0 и 1, и используется в компьютерной технике благодаря своей простоте и высо
Код Грея
Помимо двоичных чисел на практике применяются и другие коды, использующие два знака: 0 и 1. В этом разделе мы познакомимся с кодом Грея. При сортировке данных естественным представлением является о
Троичная система счисления
Троичная система счисления– позиционная система счисления с целочисленным основанием равным 3. Она существует в двух вариантах: несимметричная и симметричная трои
Восьмеричная и шестнадцатеричная системы счисления
Позиционную систему счисления можно построить по любому основанию. Однако наибольшее практическое значение имеют: двоичная, десятичная, восьмеричная и шестнадцатеричная. Причем, последние две испол
Канторово множество
Математика изобилует парадоксальными объектами. Одним из них является канторово множество. Оно описывается следующим образом. Рассмотрим единичный отрезок, показанный на рис. 3.1. Удалим из
Ковер Серпинского и снежинка Коха
Ковер Серпинского получается из единичного квадрата удалением средней части (1/3, 2/3)*(1/3, 2/3), затем удалением из каждого квадрата (i/3, i+1/3)*(j/3, j+1/3) с
Стохастические фракталы
Стохастические фракталы получаются в том случае, если в итерационном процессе случайным образом менять какие-либо параметры. При этом получаются объекты, очень похожие на природные – несимметричные
Энтропийная размерность
Пусть X – компактное пространство с метрикой d. Тогда множество называется r-плотным
Фрактал Мандельброта
Существует бесконечное множество различных фракталов. Один из них носит имя Мандельброта. Фрактал Мандельброта – это множество точек на комплексной плоскости, для которых итеративная последо
Виды доказательства
Древние греки сформулировали основные правила логического доказательства. Они различали два вида доказательства: дедукцию и индукцию. Дедукция – это доказательство от общего
Переменные и формулы в исчислении высказываний
Переменная, значениями которой являются высказывания, называется пропозициональной переменной. Понятие пропозициональной формулы вводится по индукции
Булевы функции
Функция , у которой аргументы пробегают множество {0,1} и которая принимает значение из того же множества
Предикаты
Применяемые в математике высказывания обычно представляют собой описание свойств каких-либо математических объектов или описаний отношений, существующих между этими объектами. Для анализа закономер
Семантика исчисления предикатов
Исчисление предикатов (так же как и исчисление высказываний) являются, прежде всего, языками. И эти языки можно применять не только в математике. Используя их слова, фразы и предложения, мы можем п
Правила логического вывода
Возможность логически выводить новые правильные выражения из набора истинных утверждений – это важное свойство исчисления предикатов. Логически выведенные выражения корректны, потому что они совмес
Правило резолюции
Правило резолюции (лат. resolutio – решение ): если выражения PA
Парадокс Рассела
Задание множеств характеристическим предикатом может приводить к противоречиям. Например, все рассмотренные в примерах множества не содержат себя в качестве элемента. Рассмотрим множество всех множ
Проблема континуума
Кантор был первым, кто стал рассматривать мощности (кардинальные числа) бесконечных множеств. Мощность счетного множества он обозначил древнееврейской буквой «алеф» с нулевым индексом:
Сумма нечетных чисел
Математическая индукция играет огромную роль в дискретной математике (именно в силу ее дискретного характера). Полученные этим методом доказательства в данной области математики почти столь же наде
Сумма натуральных чисел
А теперь используем метод индукции для доказательства того, что сумма первых n положительных целых чисел равна
Снова считаем подмножества
Доказывая теорему 5.1. мы неявно пользовались методом математической индукции. Теперь пришло время применить его явно. Итак, мы подозреваем, что число всех подмножеств множества из n элемент
Биномиальные коэффициенты
Слово бином означает выражение, состоящее из двух членов, например: x + y. Бином является частным случаем полинома. Биномом Ньютона наз
Треугольник Паскаля
Французский математик Блез Паскаль (1623-1662) составил таблицу из биномиальных коэффициентов. Она получилась треугольной, поскольку с увеличением степени бинома количество коэффициентов также увел
Бином Ньютона для дробных и отрицательных показателей
Формула бинома Ньютона (6.1) для целых положительных показателей была известна задолго до Исаака Ньютона (1643-1727), но им в 1676 году была указана возможность распростране
Гамма-функция
Биномиальная теорема определяет биномиальные коэффициенты через факториалы чисел n и k:
Размещения без повторений
Общее число размещений без повторений из n элементов по k элементов обычно обозначается так:
Сочетания без повторений
Число различных сочетаний без повторений обычно обозначается так: . Или так
Размещения с повторением
Если мы выбираем из множества n элементов размещения с повторениями k элементов, то в данном случае k может превосходить n.
Теорема 7.3. Об
Сочетания с повторением
Теорема 7.4. Общее число сочетаний с повторениями k элементов, взятых из совокупности n различных элементов, равно
Формула Стирлинга
Рассматривая комбинаторные задачи, мы часто сталкиваемся с факториалами. Факториал – это очень быстро растущая функция, она растет быстрее экспоненты. При достаточно больших n (n >
Подстановки
Взаимно однозначная функция называется подстановкой на
Задача Фибоначчи
Итальянский математик Леонардо Фибоначчи жил в 13 столетии и одним из первых в Европе стал использовать арабские (индийские) цифры. Он придумал несколько искусственную задачу о кроликах, которых вы
Сумма чисел Фибоначчи
Определим сумму первых n чисел Фибоначчи.
0 = 0,
0+1 = 1,
0+1+1 = 2,
0+1+1+2 = 4,
0+1+1+2+3 = 7,
0+1+1+2+3+5 = 12,
0+1+1+2+3+5+
Простые числа
Все натуральные числа, большие единицы, распадаются на два класса. К первому относятся числа, имеющие ровно два натуральных делителя, единицу и самого себя, ко второму – все остальные. Числа первог
Модулярная арифметика
В этом разделе все числа – целые. Говорят, что число a сравнимо по модулю n с числом b (обозначение
Шифрование с открытым ключом
Шифрование с открытым ключом производится следующим образом.
1. Получателем сообщений производится генерация открытого ключа (пара чисел n и e) и закрытого ключа (число d
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
,
– соответствующее множество принятых по каналу сообщений. Кодирование F, обладающее таким свойством, что
,
1, 1
, 1
1, 
– множество слов, которые могут быть получены из слова s в результате всех возможных комбинаций допустимых в канале ошибок 
, то есть 
, 
. Если 
, то та конкретная последовательность ошибок, которая позволяет получить из слова s слово 
, обозначается 
. Если тип возможных ошибок в канале подразумевается, то индекс 
, то есть необходимо и достаточно, чтобы существовало разбиение множества B* на множества 
, такое что 
.
. Обратно: по разбиению 
строится функция 
.
из всех 
двоичных последовательностей (векторов), имеющих вид
.
их сумму с помощью соотношения: 
, где 
– это сумма по модулю два.
между кодовыми словами определяется как число позиций 
таких, что 
. При построении вектора 
пары одинаковых двоичных символов 
будут давать 0 , а пары различных двоичных символов будут давать 1.
;
– «неравенство треугольника».
) и (
) на плоскости: 
.
бит можно построить 
слов: 
. Если эти слова таковы, что при всех 
:
, (7.1)
.
находится на расстоянии 
. Следовательно, если считать, что ошибки при передаче могут возникать не более чем в 
, представляет собой множество 
.
, если только 
. Тогда 
и 
.
,
называется областью декодирования для слова 
в множестве 
(
) компонент слова 
.
, то: 
, то есть
. (9.2)
. Поскольку 
, то 
; 
; 
; 
; 
.
.
.
.
.
.
. (9.3)
. Тогда:
, и из формулы (9.3) следует
. (9.4)
бит, количество которых должно удовлетворять условию (9.4). Рассматриваемый случай простейший, но одновременно практически очень важный. Таким свойством, как правило, обладают внутренние шины передачи данных в современных компьютерах.
потребуется 
дополнительных разрядов, поскольку 64=
.
Новости и инфо для студентов