Матричный метод кодирования

Рис. 2.3.

2.2. Описание декодирования и исправления ошибки по Хэммингу

Переданная по информационному каналу в приемник битовая последовательность делится на куски по n = 2r - 1 бит — получаются блоки кода. С каж­дым таким блоком выполняется операция

ci = (bi)T×M,

здесь (bi)T — строка (вместо столбца) расширенного кода. Пример приведен на рис. 2.5. Причем здесь контрольные разряды участвуют в вычислении суммы.

Если получено, что все биты ci равны нулю, то значит ошибок нет и коррекция не нужна, см. рис. 2.5. Если хотя бы один бит ci не равен нулю (см. рис. 2.6), то имела место ошибка. Значение ci преобразуют из битового представления в десятичное число i и бит блока кода с номером i — ошибочный бит (передан с ошибкой). Для исправления значение бита инвертируют: заменяют ноль на единицу, а единицу на ноль. В результате получаем правильное значение блока кода.

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

Вычисление контрольных разрядов

Рис. 2.4.

2.3. Невозможность коррекции двойных ошибок и любых ошибок большей кратности

Две и более ошибки в блоке кода Хэмминга невозможно исправить, хуже того невозможно отличить ошибку в одном бите и ошибку в двух и более битах.

Невозможность исправления двойной ошибки следует и простого факта – процедура коррекции (см. пункт 2.2.) всегда вычисляет один номер ошибочного бита, следовательно, второй и т. д. ошибочные биты просто невозможно указать. Пример двойной ошибки приведен на рис. 2.7.

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

Проверка на ошибки — нет ошибок

Рис. 2.5.

2.4. Основные недостатки кода Хэмминга

Главным недостатком кода Хэмминга является не кратность размера исходного блока кода и блока кода степени двойки. Это обстоятельство затрудняет обработку кодов Хэмминга на компьютерах, которые оперируют порциями данных кратными степени двойки (8, 16, 32, 64 бит и т. д.).

Другим недостатком является невозможность создавать код для исправления двойных ошибок или ошибок большей кратности.

Проверка на ошибки и коррекция ошибок

Пусть 9-й бит передан неправильно, см. рис. 2.5. Как видно, сумма строк вспомогательной матрицы дает номер бита с ошибкой.

Рис. 2.6.

Проверка на ошибки и невозможность коррекции ошибок кратности два и выше

Рис. 2.7.

2.2. Демонстрационная программа

2.2.1. Состав демонстрационной программы

Для лучшего понимания процесса кодирования разработана демонстрационная программа (далее просто «программа»). Программа реализована в пакете MathCAD 2001i и может работать на любой более новой версии пакета MathCAD.

Программа состоит из двух файлов

  •   «Вспомогательные функции. mcd» — содержит определения вспомогательных функций, необходимых для преобразования чисел в двоичные векторы и работы с двоичным представлением числа. Функции этой части программы здесь не описываются, ознакомится с ними и их описанием можно прямо в указанном файле.
  •   «Кодирование Хэмминга. mcd» — содержит определения основных функций для генерации кода Хэмминга и работы с этим кодом (коррекция ошибок, преобразование кода в строку символов и обратно, и т. п.). В этом же файле приведен пошаговый пример генерации кода Хэмминга из произвольной текстовой строки, пример исправления одиночных ошибок и пример невозможности исправить двойные ошибки или ошибки большей кратности.

Программа реализована для целей обучения поэтому эффективность (скорость кодирования) принесена в жертву максимальной простоте и наглядности процесса.

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

Программа состоит из следующих функций. Примеры работы каждой из функций доступны в файле «Кодирование Хэмминга. mcd» справа рядом с определение соответствующей функции.

str2vec(s) — переводит символы текстовой строки s в ASCII коды (целые числа от 0 до 255). Это встроенная функция и ее описание доступно в справке пакета MathCAD.

BinVec(v, l) — перевод вектора v, состояшего из неотрицательных целых чисел, в двоичный вектор. Каждое число преобразовывается в вектор двоичного кода длиной l. Все вектора последовательно записываются в результирующий вектор. Определение функции

Определение достаточно простое и не требует разъяснений, функция Int2Bits(x, n) определена во «Вспомогательные функции. mcd» и преобразует положительное целое число x в двоичный вектор длины n.

Nbit(r) := 2r - 1 — определение кол-ва битов n блочного кода (m, n), в который кодируются исходные по Хэммингу с числом контрольных битов r.

Mbit(r) := 2r + r - 1 — определение кол-ва битов m блочного кода (m, n), в который кодируются исходные по Хэммингу с числом контрольных битов r.

Vec2Matrix(v, m) — преобразование двоичного вектора v в массив с числом строк m. Значения исходного вектора записываются в результирующий массив по-колонкам, количество результирующих колонок определяется размером вектора v. При необходимости последняя колонка дополняется нулями. Определение функции

Vec2Vecs(v, m) — преобразование двоичного вектора v в вектор из векторов с числом элементов m. При необходимости последний вектор дополняется нулями. Определение функции

Matrix2Vec(M) — преобразование матрицы M в вектор значений. Значения записываются по-столбцам. Определение функции

InitialCodes(str, r) — переводит символы строки str в ASCI коды и преобразует их к двоичному представлению (8 бит на символ), полученный массив разделяет на блоки по m в соответствии со значением r. Возвращает матрицу из m строк, каждый из столбцов которой заполнен блоком из m бит, последний столбец может быть неполным (дополняется нулями). Определение функции

errCheckBlock(b, n, msg) — вспомогательная функция контроля размера блока кода. Проверяет, что матрица b состоит из n строк, если это не так, то возвращается ошибка. Также проверяется, что блок содержит только нули и единицы. Определение функции

ExpandBlock(b, r) — преобразует матрицу b из m строк в матрицу из Nbit(r) строк, вставляя в нее r строк (контрольных разрядов) на позициях 2i, где i = 0 .. (r – 1). Определение функции

BuildM(r) — построение матрицы M для вычисления контрольных разрядов кода Хэмминга с числом контрольных разрядов r. Определение функции

AddControlCodes(b, r) — заполнение контрольных битов кода Хэмминга в матрице b, число контрольных битов r. Определение функции

Codes2Str(codes) — перевод матрицы кодов Хэмминга codes в строку символов. Определение функции

Str2HamingCodes(str, r) — преобразование cтроки символов str в матрицу кодов Хэмминга с числом контрольных битов r. Определение функции

DetectErrors(b, r) — обнаружение и корректировка ошибок в коде Хэмминга bk с числом контрольных разрядов r. Определение функции

HamBlock2Block(b, r) — из массива кодов Хэмминга b выделяет исходный код (удаляет контрольные биты, r штук) и возвращает матрицу с исходными кодами. Определение функции

StrEncodeHam(str, r) — кодирует символы строки str кодом Хэмминга с параметром r в ASCI коды и преобразует их к двоичному представлению (8 бит на символ), полученный массив разделяет на блоки по m в соответствии со значением r. Возвращает матрицу из m строк, каждый из столбцов которой заполнен блоком из m бит - кодом Хэмминга. Последний столбец может быть неполным (дополняется нулями). Определение функции

StrEncodeHam2Str(str, r) — кодирует символы строки str кодом Хэмминга с параметром r в ASCI коды и преобразует их к двоичному представлению (8 бит на символ), полученный массив разделяет на блоки по m в соответствии со значением r, преобразует полученный код в строку символов. Возвращает строку символов. Длина строки больше, чем исходная строка из-за дополнительных разрядов. Определение функции

2.2.3. Описание функций построения матрицы для матричного кодирования Хэминга

Кодирование Хэмминга может быть представлено матричной операцией:

b = E×a,

где a – двоичный вектор исходного блока кода; b – двоичный вектор блока кода Хэмминга; E – кодирующая матрица.

Для полноты описания кодирования в программу включены функции для построения кодирующей матрицы кода Хэмминга. Эти функции позволяют кодировать по Хэммингу с большей скоростью, чем описанные в пункте 2.2.2. функции.

haBuildMatrix(r) — строит матрицу M для вычисления контрольных разрядов. Старшие разряды - первые. Определение функции

haGetControlCols(M) — вычисляет столбцы контрольных разрядов для матричного кодирования Хэмминга, используя матрицу M. Определение функции

haMakeE(r) — возвращает кодирующую матрицу размером m´n для кода Хэмминга с числом контрольных разрядов r. Определение функции

haEncode(b, r) — кодирует блоки (колонки матрицы b) кодом Хэмминга с параметром r и возвращает закодированное в виде матрицы, где коды расположены в столбцах. Использует матричное кодирование (можно сравнить с ExpandBlock(b, r), BuildM(r), AddControlCodes(b, r)). Определение функции

haStrEncode(str, r) — кодирует строку str кодом Хэмминга с параметром r и возвращает закодированное в виде матрицы, где коды расположены в столбцах. Использует матричное кодирование.

Методические указания к лабораторной работе помехозащищенное кодирование. коды Хэмминга | Социальная сеть Pandia.ru

Варианты 0.n ¾ стандартные задания. Выполнение такого варианта позволяет гордо говорить: «Я делал лабораторную работу». Одно из стандартных заданий выполняется в обязательном порядке, независимо от выполнения/невыполнения заданий повышенной сложности.

Варианты 1.n ¾ задания повышенной сложности, за ПОЛНОЕ выполнение любого из них автоматически выставляется зачет по курсу. Выполнение заданий повышенной сложности ¾ по собственному желанию и только как ДОПОЛНЕНИЕ к основному. Т. е. сначала надо сделать основное, а затем ¾ повышенной сложности.

Выполненное задание состоит из

  •   отчета по лабораторной работе, где описан СОБСТВЕННЫЙ вклад в решение проблемы. Переписывать методичку и Интернет не надо.
  •   работающей программы на MathCAD. Другие варианты программ не принимаются к рассмотрению, кроме случаев, оговоренных в заданиях повышенной сложности.

Вариант 0.1

Используя методичку и программу изучить логику и пошаговое действие алгоритма Хэмминга.

Создать, используя процедуры демонстрационной программы, две функции:

1)  кодирование произвольной строки символов кодом Хэмминга в строку символов.

2)  декодирование произвольной строки символов из кода Хэмминга в исходную строку символов.

Реализовать эти функции для обеих вариантов кодирования (обычный и матричный).

Сравнить быстродействие двух реализаций.

1)  Почему невозможно создать СОВЕРШЕННЫЙ код, исправляющий двойные или тройные ошибки.

2)  Что такое квазисовершенный код и чем он отличается от совершенного.

3)  Что такое коды БЧХ и к какому клаccу кодов они относятся.

Вариант 1.1

Реализовать другой метод совершенного кодирования (код Голея). Написать руководство (в качестве примера см. настоящее руководство) и демонстрационную программу. Программы принимаются ТОЛЬКО в MathCAD.

Вариант 1.2

Реализовать метод кодирования БЧХ. Написать руководство (в качестве примера см. настоящее руководство) и демонстрационную программу. Программы принимаются ТОЛЬКО в MathCAD.

Вариант 1.3

Реализовать построение декодирующей таблицы с лидерами для кода Хэмминга.

Вариант 1.4

Реализовать построение кодирующего полинома для произвольного кода Хэмминга.

ЗАКЛЮЧЕНИЕ

Выполнив данную лабораторную работу, вы будете лучше понимать суть и методы помехозащищенного блочного кодирования.

Список Использованных источников

1.  Блейхут Р. Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986. – 576с.

2.  Н. Р. Спиричева. Теория информации. Конспект лекций. – Екб.: УМЦ УПИ, 2001. – 78с.

3.  Темников Ф. Е. Теоретические основы информационной техники. М.:Энергия, 1979.

4.  Дмитриев В. И. Прикладная теория информации. – М.: Высш. шк., 19с.

5.  Цымбал В. П. Задачник по теории информации и кодированию. Киев: Высш. шк., 19с.

6.  Питерсон У. Коды, исправляющие ошибки. – М.: Мир, 1964.

7.  Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир, 1976.

8.  Берлекэмп Э. Алгебраическая теория кодирования. – М.: Мир, 1971.

9.  Форни Д. Каскадные коды. – М.: Мир, 1970.

10.  Галлагер Р. Теория информации и надёжная связь. – М.: Сов. Радио, 1974.

11.  Мак-Вильямс Ф. Дж., Слоен Н. Дж. А. Теория кодов, исправляющих ошибки. – М.: Связь, 1979.

12.  Шеннон К. Работы по теории информации и кибернетике. – М.: Ил, 1963, с. 243-332.

13.  Хэмминг Р. В. Коды с обнаружением и исправлением ошибок. – М.: Ил, 1956, с. 7-22.

14.  Боуз Р. К., Рой-Чоудхури Д. К. Об одном классе двоичных групповых кодов с исправлением ошибок. – В кн. Кибернетический сборник. Вып. 2. – М.: Ил. 1962, 83-94.

15.  Гоппа В. Д. Новый класс линейных корректирующих кодов. – Проблемы передачи информации, 1970, вып. 3, с. 24-30.

16.  Кердок А. М. Класс нелинейных двоичных кодов с низкой скоростью передачи. М.: Мир, 1973, с. 33-38.

17.  Витерби А. Границы ошибок для свёрточных кодов и асимптотически оптимальный алгоритм декодирования. – М.: Мир, 1970, с. 142-165.

18.  http: //kunegin. *****/ref3/code.

pandia.ru

Матричный декодер

Матричная расшифровка - аудио технология, где конечное число дискретных аудио каналов (например, 2) расшифрованы в большее число каналов на, воспроизводят (например, 5). Каналы обычно, но не всегда, устроил передачу или запись кодирующим устройством, и расшифровал для воспроизведения декодером.

Функция должна позволить многоканальному аудио, такому как квадрафонический звук или «звук вокруг» быть закодированным в сигнале стерео, и таким образом воспроизведенным как стерео на оборудовании стерео, и как окружают на, окружают оборудование – это - «совместимое» многоканальное аудио.

Процесс

Матричное кодирование не позволяет кодировать несколько каналов в меньшем количестве каналов, не теряя информацию: нельзя вместить 5 каналов в 2 (или даже 3 в 2), не теряя информацию, поскольку это теряет размеры: расшифрованные сигналы весьма зависимы. Идея состоит в том, чтобы скорее закодировать что-то, что и будет приемлемым приближением «звука вокруг», когда расшифровано, и приемлемый (или еще выше) стерео.

Примечание

Примечание для матричного кодирования состоит из числа оригинальных дискретных аудио каналов, отделенных двоеточием от числа закодированных и расшифрованных каналов. Например, четыре канала, закодированные в два дискретных канала и расшифрованные назад к четырем каналам, были бы записаны нотами:

4:2:4

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

5:5:6

Много матричных декодеров используют в своих интересах эффект Хааса, а также аудио реплики, врожденные от исходных каналов.

Различные матрицы кодирования описаны ниже.

Матрица Dynaquad (2:2:4) / (4:2:4)

Главным образом используемый в качестве простого метода для получения обходной каналов информации из нормальной записи стерео (2:2:4), эта матрица также использовалась для определенного кодирования 4 звуковых каналов в некоторых альбомах (4:2:4).

Расшифровка матрицы

КВ. матрица, «Квадрафонический Стерео», CBS, КВ. (4:2:4)

изменение фазы, изменение фазы

У

основной КВ. матрицы были моно/стерео аномалии, а также проблемы кодирования/расшифровки, в большой степени подвергшие критике Майклом Джерзоном и другими.

Попытка улучшить систему приводит к использованию других кодирующих устройств или звуковых методов захвата, все же матрица расшифровки осталась неизменной.

Кодирующее устройство положения

Кодирующее устройство N/2, которое закодировало каждое положение в кругу на 360 ° - у него было 16 входов, и каждый мог быть набран к точному желаемому направлению, произведение оптимизированного кодирует.

Ориентированное форвардами кодирующее устройство

изменение фазы, изменение фазы

Ориентированное форвардами кодирующее устройство заставило Центр Назад быть закодированным как Фронт Центра и рекомендовалось для использования прямого репортажа для максимальной моно совместимости - это также закодировало Центр, Уехал/Сосредоточил Право и оба диагональных разделения оптимальным способом.

Мог использоваться, чтобы изменить существующие записи стерео с 2 каналами и создать 'синтезируемый КВ.', что, когда играется через декодер Полной Логики или Тейта ДЕ СК, показал 180 °, или 270 ° синтезировали квадрафонический эффект. Много радиостанций FM стерео, вещающих КВ. в 70-х, использовали свое Ориентированное форвардами КВ. кодирующее устройство для этого. Для КВ. декодеров CBS проектировала схему, которая произвела улучшение на 270 °, используя фазовращатели на 90 ° в декодере. У Кодирующих устройств Сэнсуи QS и Vario-матричных Декодеров QS была подобная способность.

Назад ориентированное кодирующее устройство

изменение фазы, изменение фазы

Назад ориентированное Кодирующее устройство было переменой Ориентированного форвардами Кодирующего устройства - это позволило звукам быть помещенными оптимально в спине половина комнаты, но моносовместимость была принесена в жертву.

Когда используется со стандартными записями стерео это создало «дополнительный широкий» стерео со звуками вне спикеров.

У

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

Лондонская коробка

Это закодировало Центр Назад таким способом, которым это не отменяло в моно воспроизведении, таким образом его продукция обычно смешивалась с тем из Кодирующего устройства Положения или Передового Ориентированного кодирующего устройства. После 1972, подавляющее большинство КВ. Закодированных альбомов были смешаны или с Кодирующим устройством Положения или с Ориентированным форвардами кодирующим устройством.

Гентский микрофон

Кроме того, CBS создала КВ. Гентский Микрофон, который был пространственной системой микрофона, используя Неймана микрометр QM-69. Сигналы от QM-69 были differenced, и затем фазой-matrixed в КВ. с 2 каналами

С Гентским Микрофоном, КВ., был преобразован от Матрицы в Ядро, и дополнительный сигнал мог быть получен, чтобы обеспечить работу N:3:4.

КВ. Universal

В 1976 Бен Бауэр объединил матричные и дискретные системы в USQ или Универсальный КВ.

Это были иерархические 4-4-4 дискретных матрицы, которые использовали КВ. матрицу в качестве основной полосы частот для дискретных квадрафонических передач FM, используя дополнительные сигналы различия, названные «T» и «Q». Для передачи FM USQ дополнительная «T» модуляция была помещена в 38 кГц в квадратуре к стандартному сигналу различия стерео, и «Q» модуляция была помещена в перевозчик в 76 кГц. Для стандартных КВ. Матричных передач с 2 каналами CBS рекомендовала, чтобы дополнительный экспериментальный тон был помещен в 19 кГц в квадратуре к регулярному экспериментальному тону, чтобы указать на КВ. кодируемые сообщения и активировать декодер Логики слушателей.

CBS утверждала, что КВ. система должна быть отобрана как стандарт для квадрафонического FM потому что, в аудировании FCC различных четырех предложений по каналу вещания, 4:2:4 КВ. система, расшифрованная с декодером Параматрицы CBS, у которого побеждают 4:3:4 (без логики), а также все другой 4:2:4 (с логикой) проверенные системы, приблизившись к исполнению дискретной главной ленты в пределах очень небольшого края. В то же время КВ. «сгиб» к стерео и моно был предпочтен и моно «сгибу» стерео 4:4:4, 4:3:4 и все другой 4:2:4 системы кодирования.

Тейт декодер DES

Направленная Система Улучшения, также известная как Тейт DES, была продвинутым декодером, который увеличил directionality основной КВ. матрицы.

Это сначала matrixed четыре продукции КВ. декодера, чтобы получить дополнительные сигналы, затем сравнил их конверты, чтобы обнаружить преобладающее направление и степень господства.

Секция процессора, осуществленная за пределами жареного картофеля Тейта ИКА, применила переменный выбор времени нападения/распада к управляющим сигналам и определила коэффициенты «B» (Смесь), матрицы должны были увеличить directionality. На них реагировали истинные аналоговые множители в Матричном IC's Множителя, чтобы умножить поступающую матрицу на «B» матрицы и произвести продукцию, в которой были увеличены directionality всех преобладающих звуков.

Так как DES мог признать все три направления энергетической Сферы одновременно и увеличить разделение, у этого было очень открытое и 'дискретное' зондирование soundfield.

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

Система Долби использовала Тейта IC's DES в их театральных процессорах приблизительно до 1986, когда они разработали Про Логическую систему. К сожалению, задержки и проблемы сохраняли Тейта IC's DES от рынка до, конец 70-х и только двух потребительских декодеров когда-либо делался, который нанял их, Audionics Space & Image Composer и Фосгэйта Тейта II 101 А. Фосгэйт использовал более быструю, обновленную версию IC, названного Тейтом II и дополнительной схемой, которая предусмотрела улучшение разделения вокруг полных 360 soundfield. В отличие от более ранних Полных Соответствующих волне Логических декодеров для КВ., который изменил уровни продукции, чтобы увеличить directionality, Тейт, которого DES отменил КВ. перекрестную связь сигнала как функцию преобладающего directionality, держа недоминирующими звуками и реверберацией в ее надлежащих пространственных местоположениях на их правильном уровне.

Матрица QS, «Регулярная Матрица», «Квадрафонический Звук» (4:2:4)

изменение фазы, изменение фазы

j = Изменение фазы на 20 °

k = Изменение фазы на 25 °

l = Изменение фазы на 55 °

m = Изменение фазы на 115 °

Ambisonic UHJ ядро (3:2:4 или больше)

изменение фазы, изменение фазы

Стерео системы Долби и система Долби окружают (матрица 4:2:4)

Стерео системы Долби и система Долби Окружают, также известны как член парламента системы Долби, система Долби SVA и Про Логика.

изменение фазы, изменение фазы

Система Долби матрица SVA является настоящим именем Стерео системы Долби 4:2:4 кодирование матрицы.

Термин «Окруж системы Долби» относится и к кодированию и к расшифровке в домашней обстановке, в то время как в театре это известно «Стерео системы Долби», «Матрица Кинофильма системы Долби» или «член парламента системы Долби».

Оригинальная «система Долби Окружает» домашнее внедрение, опустил канал центра, и только смешанный стерео, чтобы Окружить 3.0 (Левый, Правильный, Окружить). Все же используемая матрица является тем же самым.

«Про Логика» относится к используемому декодеру, нет никакой специальной Про матрицы кодирования Логики.

ru.knowledgr.com

Презентация на тему: "Цель: знакомство с матричным способом кодирования и декодирования информации. Задачи: изучить понятия: матрица; кодирующая матрица; произведение матриц.". Скачать бесплатно и без регистрации.

Похожие презентации

Показать еще

Презентация на тему: " Цель: знакомство с матричным способом кодирования и декодирования информации. Задачи: изучить понятия: матрица; кодирующая матрица; произведение матриц." — Транскрипт:

1

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

3 Матрица – это прямоугольная таблица, составленная из элементов, имеющих произвольную природу. Матрицей размера mn называется прямоугольная таблица чисел, содержащая m строк и n столбцов. Матрица, в которой одинаковое количество строк и столбцов, называется квадратной.

4 Будем использовать матрицы размером 2*2. Для того, чтобы воспользоваться способом шифровки с помощью матриц, достаточно уметь считать на уровне 6 класса, знать порядок букв в алфавите и правило умножения матриц. Расшифровать же его смогут только с помощью компьютера.

5 Для кодировки текста на русском языке пронумеруем все буквы по месту их расположения в алфавите – от 1 до 33, знак, пробел, тире, точка и т. д.(исходя из послания).

6 Поменяем каждую букву на число. Получим: 33, 34, 10, 34, 26, 10, 22, 18 Построим из этой последовательности две матрицы: Зашифруем это сообщение с помощью еще одной матрицы - кодирующая матрица

7 Тогда можно передать адресату сообщение: 96, 170, 53,102, 118, 74, 70, 46.

8 Получим 33, 34, 10, 34, 26, 10, 22, 18, что после перевода в буквы будет означать Я и шифр.

9 Вычислите произведения: Проверить

myshared.ru

Кодирование информации

3.2 Представление кодов в виде кодовых деревьев

3.3 Представление кодов в виде многочленов

3.4 Геометрическое представление кодов

1. Кодирование. Основные понятия и определения

Рассмотрим основные понятия, связанные с кодированием информации. Для передачи в канал связи сообщения преобразуются в сигналы. Символы, при помощи которых создаются сообщения, образуют первичный алфавит, при этом каждый символ характеризуется вероятностью его появления в сообщении. Каждому сообщению однозначно соответствует сигнал, представляющий определенную последовательность элементарных дискретных символов, называемых кодовыми комбинациями. Кодирование - это преобразование сообщений в сигнал, т.е. преобразование сообщений в кодовые комбинации. Код - система соответствия между элементами сообщений и кодовыми комбинациями. Кодер - устройство, осуществляющее кодирование. Декодер - устройство, осуществляющее обратную операцию, т.е. преобразование кодовой комбинации в сообщение. Алфавит - множество возможных элементов кода, т.е. элементарных символов (кодовых символов) X = {xi}, где i = 1, 2,..., m. Количество элементов кода - m называется его основанием. Для двоичного кода xi = {0, 1} и m = 2. Конечная последовательность символов данного алфавита называется кодовой комбинацией (кодовым словом). Число элементов в кодовой комбинации - n называется значностью (длиной комбинации). Число различных кодовых комбинаций (N = mn) называется объемом или мощностью кода.

Если N0 - число сообщений источника, то N ³ N0. Множество состояний кода должно покрывать множество состояний объекта. Полный равномерный n - значный код с основанием m содержит N = mn кодовых комбинаций. Такой код называетсяпримитивным.

Коды можно классифицировать по различным признакам:

1. По основанию (количеству символов в алфавите): бинарные (двоичные m=2) и не бинарные (m ¹ 2).

2. По длине кодовых комбинаций (слов):

равномерные - если все кодовые комбинации имеют одинаковую длину;

неравномерные - если длина кодовой комбинации не постоянна.

3. По способу передачи:

блочные - данные сначала помещаются в буфер, а потом передаются в канал и бинарные непрерывные.

4. По помехоустойчивости:

простые (примитивные, полные) - для передачи информации используют все возможные кодовые комбинации (без избыточности);

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

5. В зависимости от назначения и применения условно можно выделить следующие типы кодов:

Внутренние коды - этокоды, используемые внутри устройств. Это машинные коды, а также коды, базирующиеся на использовании позиционных систем счисления (двоичный, десятичный, двоично-десятичный, восьмеричный, шестнадцатеричный и др.). Наиболее распространенным кодом в ЭВМ является двоичный код, который позволяет просто реализовать аппаратно устройства для хранения, обработки и передачи данных в двоичном коде. Он обеспечивает высокую надежность устройств и простоту выполнения операций над данными в двоичном коде. Двоичные данные, объединенные в группы по 4, образуют шестнадцатеричный код, который хорошо согласуется с архитектурой ЭВМ, работающей с данными кратными байту (8 бит).

Коды для обмена даннымии их передачи по каналам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII - это 7-битный код буквенно-цифровых и других символов. Поскольку ЭВМ работают с байтами, то 8-й разряд используется для синхронизации или проверки на четность, или расширения кода. В ЭВМ фирмы IBM используется расширенный двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code).

В каналах связи широко используется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.).

При кодировании информации для передачи по каналам связи, в том числе внутри аппаратным трактам, используются коды, обеспечивающие максимальную скорость передачи информации, за счет ее сжатия и устранения избыточности (например: коды Хаффмана и Шеннона-Фано), и коды обеспечивающие достоверность передачи данных, за счет введения избыточности в передаваемые сообщения (например: групповые коды, Хэмминга, циклические и их разновидности).

Коды для специальных применений - это коды, предназначенные для решения специальных задач передачи и обработки данных. Примерами таких кодов является циклический код Грея, который широко используется в АЦП угловых и линейных перемещений. Коды Фибоначчи используются для построения быстродействующих и помехоустойчивых АЦП.

Основное внимание в курсе уделено кодам для обмена данными и их передачи по каналам связи.

ЦЕЛИ КОДИРОВАНИЯ:

1) Повышение эффективности передачи данных, за счет достижения максимальной скорости передачи данных.

2) Повышение помехоустойчивости при передаче данных.

В соответствии с этими целями теория кодирования развивается в двух основных направлениях:

1. Теория экономичного (эффективного, оптимального) кодирования занимается поиском кодов, позволяющих в каналах без помех повысить эффективность передачи информации за счет устранения избыточности источника и наилучшего согласования скорости передачи данных с пропускной способностью канала связи.

2. Теория помехоустойчивого кодированиязанимается поиском кодов, повышающих достоверность передачи информации в каналах с помехами.

В зависимости от применяемых методов кодирования, используют различные математические модели кодов, при этом наиболее часто применяется представление кодов в виде: кодовых матриц; кодовых деревьев; многочленов; геометрических фигур и т.д.

3.1 Матричное представление кодов

Используется для представления равномерных n - значных кодов. Для примитивного (полного и равномерного) кода матрица содержит n - столбцов и 2n - строк, т.е. код использует все сочетания. Для помехоустойчивых (корректирующих, обнаруживающих и исправляющих ошибки) матрица содержит n - столбцов (n = k+m, где k-число информационных, а m - число проверочных разрядов) и 2k - строк (где 2k - число разрешенных кодовых комбинаций). При больших значениях n и k матрица будет слишком громоздкой, при этом код записывается в сокращенном виде. Матричное представление кодов используется, например, в линейных групповых кодах, кодах Хэмминга и т.д.

3.2 Представление кодов в виде кодовых деревьев

 

Кодовое дерево - связной граф, не содержащий циклов. Связной граф - граф, в котором для любой пары вершин существует путь, соединяющий эти вершины. Граф состоит из узлов (вершин) и ребер (ветвей), соединяющих узлы, расположенные на разных уровнях. Для построения дерева равномерного двоичного кода выбирают вершину называемую корнем дерева (истоком) и из нее проводят ребра в следующие две вершины и т.д.

Пример кодового дерева для полного кода приведен на рис.1.

                                       1                                          0

      1          0                  1           0                  1          0                  1               0

  111           110            101          100         011             010         001        000

Рис.1. Дерево для полного двоичного кода при n = 3

Дерево помехоустойчивого кода строится на основе дерева полного кода путем вычеркивания запрещенных кодовых комбинаций. Для дерева неравномерного кода используется взвешенный граф, при этом на ребрах дерева указываются вероятность переходов. Представление кода в виде кодового дерева используется, например, в кодах Хаффмена.

Представление кодов в виде полиномов основано на подобии (изоморфизме) пространства двоичных n - последовательностей и пространства полиномов степени не выше n - 1.

Код для любой системы счисления с основанием Х может быть представлен в виде:

 

G (x) = an-1 xn-1+ an-2 xn-2+... + a1 x+ a0 =,

где аi - цифры данной системы счисления (в двоичной 0 и 1);

х - символическая (фиктивная) переменная, показатель степени которой соответствует номерам разрядов двоичного числа-

Например: Кодовая комбинация 1010110 может быть представлена в виде:

G (x) =1×x6+0×x5+1×x4+0×x3+1×x2+1×x1+0×x0 =x6+x4+x2+x=10101

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

Любая комбинация n - разрядного двоичного кода может быть представлена как вершина n - мерного единичного куба, т.е. куба с длиной ребра равной 1. Для двухэлементного кода (n = 2) кодовые комбинации располагаются в вершинах квадрата. Для трехэлементного кода

(n = 3) - в вершинах единичного куба (рис.2).

В общем случае n мерный куб имеет 2nвершин, что соответствует набору кодовых комбинаций 2n.

n = 2 n = 3

Рис.2. Геометрическая модель двоичного кода

Геометрическая интерпретация кодового расстояния. Кодовое расстояние - минимальное число ребер, которое необходимо пройти, чтобы попасть из одной кодовой комбинации в другую. Кодовое расстояние характеризует помехоустойчивость кода.

1.         Кловский Д.Д. Теория передачи сигналов. -М.: Связь, 1984.

2.         Кудряшов Б.Д. Теория информации. Учебник для вузов Изд-во ПИТЕР, 2008. - 320с.

3.         Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. - 1999. - Т.35, Вып. - С.95 - 108.

4.         Семенюк В.В. Экономное кодирование дискретной информации. - СПб.: СПбГИТМО (ТУ), 2001

5.         Дмитриев В.И. Прикладная теория информации. М.: Высшая школа, 1989.

6.         Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: МАИ, 1992.

7.         Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М.: Наука, 2006.

vevivi.ru

Статьи по теме