Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика)




НазваниеКонспект лекций для студентов заочной формы обучения направления 080201 (Информатика)
страница10/11
Дата публикации23.05.2013
Размер0.94 Mb.
ТипКонспект
uchebilka.ru > Информатика > Конспект
1   2   3   4   5   6   7   8   9   10   11
^

3.9 Вес и расстояние Хэмминга. Способность кодов обнаруживать и исправлять ошибки



Пусть u=(u1, u2, , un) – двоичная последовательность длиной n.

Число единиц в этой последовательности называется весом Хэмминга вектора u и обозначается как (u).

Например: u=(1 0 0 1 0 1 1), тогда (u)=4.
Пусть u и v – двоичные слова длиной n.

Число разрядов, в которых эти слова различаются, называется расстоянием Хэмминга между u и v и обозначается как d(u, v).

Например: u=(1 0 0 1 0 1 1), v=(0 1 0 0 0 1 1), тогда d(u, v)=3.
Легко видеть, что расстояние между двоичными последовательностями u и v равно весу их поразрядной суммы, т. е.

d(u, v)=(u+v). (3.9)
Вероятность того, что слово v будет принято за u, равна
Рош=рn-d(u, v)qd(u, v), (3.10)
где p – вероятность правильной передачи бита сообщения; q=1-p – вероятность ошибки.
Задав линейный код, т. е., определив все 2k кодовые слова, можно определить расстояние между всеми возможными парами кодовых слов, минимальное из них называется минимальным кодовым расстоянием dmin.

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

Тогда, минимальное кодовое расстояние dmin равно минимальному весу Хэмминга для всех строк порождающей матрицы кода.
Для возможности обнаружения ошибки в одной позиции минимальное кодовое расстояние между словами должно быть больше 1, иначе ошибка в одной позиции может перевести одно кодовое слово в другое, что не даст её обнаружить.
Для обнаружения кодом ошибок кратности не больше l необходимо и достаточно, чтобы минимальное расстояние между его словами было l+1:
dmin l+1 . (3.11)
Для исправления кодом ошибок кратности, не больше l, необходимо и достаточно, чтобы наименьшее расстояние между его словами было 2l+1:
dmin ≥ 2l+1. (3.12)

Установлено, что в линейном (k, n)-коде, минимальное расстояние между кодовыми словами которого равно 2l+1, значения n - длины кодовой последовательности, r=n-k - числа дополнительных разрядов и l - кратности ошибки, обнаруживаемой кодом, должны соответствовать неравенству
, (3.13)
которое называется нижней границей Хэмминга.
Кроме того, если параметры n, r и l соответствуют неравенству
, (3.14)

которое называется верхней границей Варшамова-Гильберта, то существует (n-r, n)-код, исправляющий все ошибки веса l и менее.

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

Верхняя граница задаёт достаточные условия для существования помехоустойчивого кода.
Для линейных блочных (k, n)-кодов с минимальным расстоянием dmin существует нижняя граница Плоткина, устанавливающая минимальное количество проверочных символов r при n ≥ 2dmin-1:
. (3.15)

Наконец, исходя из вышеизложенного, сформулируем правила построения порождающей матрицы линейного блочного (k, n) - кода:

  1. количество исходных кодовых комбинаций (число строк) порождающей матрицы равно k, т. е. количеству информационных элементов;

  2. все кодовые комбинации порождающей матрицы должны быть различны, причём нулевая комбинация в их состав не включается;

  3. все кодовые комбинации порождающей матрицы линейно независимы;

  4. количество единиц в каждой кодовой комбинации порождающей матрицы должно быть  dmin;

  5. кодовое расстояние между какими-либо парами кодовых слов должно быть  dmin.

Таким образом, порождающая матрица линейного систематического блочного кода составляется из двух подматриц: информационной подматрицы Ik×k (которую удобно представлять в виде единичной матрицы) и проверочной подматрицы Рkr.

Проверочная подматрица Pk(n-k) составляется подбором r-разрядных комбинаций с количеством единиц в строке ≥ dmin-1 и кодовым расстоянием между строками ≥ dmin-2.


1   2   3   4   5   6   7   8   9   10   11

Похожие:

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций 2007 Экология. Конспект лекций. Для студентов специальностей...
Экология. Конспект лекций. Для студентов специальностей 080201 «Информатика», 090220 «Оборудование химических производств и предприятий...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций по дисциплине “политэкономия” для студентов 050107 заочной формы обучения
Конспект лекций по дисциплине “Политэкономия” для студентов 050107 заочной формы обучения/ Разраб. Овечкина Е. А. Северодонецк, 2000....

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций в схемах по дисциплине «организация труда менеджера»
Конспект лекций в схемах по дисциплине «Организация труда менеджера» (для студентов (для студентов 4 курса дневной и 3 курса заочной...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconХарьковская национальная академия городского хозяйства
Конспект лекций для студентов 1-го курса дневной и заочной формы обучения образовательно-квалификационного уровня бакалавр, направления...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций в схемах по дисциплине «управление персоналом»
Конспект лекций в схемах по дисциплине «Управление персоналом» (для студентов 5 курса направления подготовки 0502 “Менеджмент” специальности...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций по курсу Начертательная геометрия
Конспект лекций по курсу начертательная геометрия (для студентов заочной формы обучения всех специальностей академии). Сост. Лусь...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций по курсу «Организация производства»
Конспект лекций по курсу «Организация производства» (для студентов и слушателей заочной формы обучения фпоизо специальностей 050100...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций для студентов бакалавратуры 0902 «Инженерная механика» заочной формы обучения
Сила давления жидкости на криволинейные цилиндрические поверхности

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconМетодические указания для выполнения лабораторных, самостоятельных...
«Информатика и компьютерная техника» (для студентов 1-го и 2-го курсов заочной формы обучения образовательно-квалификационного уровня...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconА. Г. Шкаев твердотельная электроника
Конспект лекций предназначен для студентов очной, очно-заочной и заочной форм обучения

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<