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




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

3.2 Линейные блочные коды



Для блочного кода с 2k кодовыми словами длиной n символов, если он не обладает специальной структурой, аппарат кодирования/ декодирования оказывается очень сложным. Одним из условий практической реализуемости блочного кода является условие его линейности.

Определение. Блочный код длиной n символов, представляющий множество 2k кодовых слов, называется линейным (k, n)-кодом при условии, что все его кодовые слова образуют k-мерное подпространство векторного пространства n-последовательностей двоичного поля GF(2).

Иными словами, двоичный код является линейным, если поразрядная сумма по модулю 2 (mod 2)i двух кодовых слов также является кодовым словом данного кода.

Желательным качеством линейных блочных кодов является систематичность. Систематический код имеет неизменную информационную часть длиной k символов и избыточную (проверочную) часть длиной n-k символов (рис. 3.1).


^

3.2.1 Основные понятия двоичной арифметики



Полем называется множество математических объектов, для которых определены операции сложения, вычитания, умножения и деления.

Возьмем простейшее поле из двух элементов 0 и 1. Определим для него операции сложения и умножения следующим образом:

0+0=0,

0+1=1,

1+0=1,

1+1=0;




0*0=0,

0*1=0,

1*0=0,

1*1=1.



Определенные таким образом операции сложения и умножения называются сложением по модулю 2 (mod 2) и умножением по модулю 2.

Из равенства 1+1=0 следует, что -1=1 и 1+1=1-1, а из равенства 1*1=1 – что 1:1=1.

Алфавит из двух символов 0 и 1 вместе с операциями сложения и умножения по mod 2 называется двоичным полем GF(2). К полю GF(2) применимы все методы линейной алгебры, в том числе матричные операции.

Операция сложения по модулю два обычно обозначается символом . В данном курсе в дальнейшем будет использоваться только сложение по модулю два, которое для удобства будем обозначать обычным знаком +.

^

3.3 Код с проверкой на четность



Самый простой линейный блочный код – это (n-1, n) - код с контролем четности. Данный код, в частности, широко используется в модемах.

Кодирование заключается в добавлении к каждому байту 9-го бита таким образом, чтобы дополнить количество единиц в байте до заранее выбранного для кода четного (even) или нечетного (odd) значения.
Например, информационная последовательность (101), тогда кодовой последовательностью будет (1010), где проверочный символ формируется путем суммирования по mod 2 символов информационной последовательности. Заметим, что если число единиц в информационной последовательности четно, то результатом суммирования по mod 2 будет 0, если нечетно – то 1, т.е. проверочный символ дополняет кодовую последовательность так, чтобы количество единиц в ней было четным.

Математически схему кодирования с проверкой на четность можно описать следующим образом:
Е(m1, ..., mk)= m1, ..., mk, mk+1, где
Таким образом, количество единиц в принятой последовательности должно быть четным, т. е. .

Схему декодирования можно представить как


Введем определение двоичного симметричного канала, для которого ошибки в битах равновероятны и независимы. Схематически двоичный симметричный канал представлен на рис. 3.2, где р – вероятность безошибочной передачи бита сообщения; q=1-p – вероятность ошибочной передачи.



Рисунок 3.2
Для такой схемы передачи данных вероятность того, что в n-позиционном коде произойдет только одна ошибка, составит .

В общем случае вероятность передачи n битов с k ошибками определяется формулой Бернулли
, (3.1)

где - число сочетаний из n по k.

Заметим, что код с проверкой четности не обнаруживает ошибки кратности 2, так как если в переданной последовательности произошло 2, 4 и т.д. ошибки, независимо в какой позиции, то общее число единиц в принятой последовательности будет четным, и ошибки обнаружены не будут. Однако вероятность двойной ошибки значительно меньше одиночной. Покажем это на простом примере.
^ Пример. Проверка четности при k=2 реализуется следующим кодом: 00000, 01011, 10101, 11110.
Обозначим как р – вероятность правильной передачи, q – вероятность ошибочной передачи бита сообщения.

Тогда вероятность возникновения хотя бы одной ошибки в кодовой последовательности длиной 3 бита равна q3+3pq2+3p2q. Из них не будут обнаружены ошибки в двух битах, не изменяющих четности, вероятность которых Pош=3pq2.

Вероятность ошибочной передачи сообщения из двух битов без использования контроля четности составляет Pош=q2+2pq.

При использовании достаточно надежного канала передачи данных, т. е. при q <<1, 3pq2 <<q2+2pq, что говорит о целесообразности использования помехоустойчивого кодирования с обнаружением однократных ошибок.

Несмотря на свою простоту и не очень высокую эффективность, коды с проверкой на четность широко используются в системах передачи и хранения информации. Они ценятся за невысокую избыточность: достаточно добавить к передаваемой последовательности один избыточный символ – и можно определить, есть ли в принятой последовательности ошибка. Однако локализовать место, где произошла ошибка, а следовательно, ее исправить пока не удается. Можно лишь повторить передачу слова, в котором возникла ошибка, и тем самым ее исправить.


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
Главная страница


<