Коды Хемминга. Функциональные схемы кодирующих и декодирующих устройств линейных кодов
1. Построить код Хемминга, взяв в качестве исходной кодовой комбинации двоичное число, полученное из двух последних цифр шифра студента. Определить вероятность ошибочного приема полученной комбинации кода Хемминга и вероятность появления необнаруживаемой ошибки.
2. Дать общую характеристику и классификацию корректирующих кодов.
3. Изложить принципы построения кодов, обнаруживающих и исправляющих ошибки (итеративные, циклические, Хемминга).
4. Изложить функциональную схему кодирующего устройства кода Хемминга.
Избыточное кодирование служит для повышения достоверности приема дискретной информации в реальных системах связи при наличии помех. При таком кодировании принимаются корректирующие (помехозащищенные) коды, в которых все используемые для передачи информации комбинации (разрешенные кодовые комбинации) отличаются друг от друга не менее, чем в двух разрядах. Комбинации, не используемые для передачи информации, принадлежат к числу запрещенных. В корректирующих кодах один неправильно принятый разряд приводит к замене разрешенной кодовой комбинации, неразрешенной для данного кода.
|
|
Любой корректирующий код содержит n элементов, из которых k информационных и r проверочных (информации не несут). Тогда n = k+r.
Код Хемминга относится к блочным разделимым систематическим корректирующим кодам. Его проверочные элементы формируются путем суммирования по модулю два (проверка на четность).
Длину кодовой комбинации n кода Хемминга при заданном числе информационных элементов k можно определить из неравенства
2k ≤
Рассмотрим принцип построения кодовой комбинации кода Хемминга, если шифр студент 87-ЭТ-7.
Учитывая, что в шифре содержится только одна цифра 7, к ней необходимо добавить цифры 1 и 0. В этом случае шифр будет иметь вид 87-ЭТ-107.
Выразим полученное число в двоичной форме счисления путем последовательного деления числа 107 на 2:
Так как последний остаток есть коэффициент при основании системы с наивысшей степенью, то число 107 в двоичной системе счисления записывается в виде 11010011 (смотри числители остатков). Следовательно, исходная кодовая комбинация будет иметь семь элементов (k=7).
Определим число проверочных элементов из неравенства
27
Отсюда n = 11, r = 4. Следовательно, кодовая комбинация будет содержать 11 элементов, из которых 7 информационных, а 4 проверочных.
Определим позиции проверочных элементов в кодовой комбинации. Для этого запишем номера позиций кодовой комбинации в двоичной системе счисления – табл.2.
|
|
Таблица 2
N позиции | Двоичное число | |||
Из табл.2 находим, что единицу в первом разряде имеют все нечетные номера позиций кодовой комбинации.
Следовательно, первая проверка по модулю два должна охватывать все нечетные номера позиций:
S1 = α1 α3 α5 α7 α9 α11
Проверочным элементом является первая позиция кодовой комбинации, е ее значение можно определить из выражения
α1 = α3 α5 α7 α9 α11
Результат второй проверки определяет второй разряд двоичного числа. Из табл.2 находим все номера позиций, имеющие единицу во втором разряде:
S2 = α2 α3 α6 α7 α10 α11
Проверочным элементом является вторая позиция:
α2 = α3 α6 α7 α10 α11
Рассуждая аналогично, найдем номера позиций третьей и четвертой проверок, а также проверочные элементы:
S3 = α4 α5 α6 α7 α4 = α5 α6 α7
S4 = α8 α9 α10 α11 α8 = α9 α10 α11
Cледовательно, проверочными элементами являются 1-я, 2-я, 4-я, 8-я позиции, а остальные – информационными. Тогда информационные элементы будут иметь значения:
α3 = 1, α5 = 1, α6 = 0, α7 = 1, α9 = 0, α10 = 1, α11 = 1.
Определим значения проверочных элементов:
α1 = 1 1 1 0 1 = 0 α2 = 1 0 1 1 1= 0;
α4 = 1 0 1 = 0; α8 = 0 1 1 = 0.
В результате получим комбинацию кода Хемминга 00101010011, которая будет передана в канал связи.
На рисунке представлена функциональная схема кодирующего устройства кода Хемминга для рассмотренного случая. После построения функциональной схемы кодирующего устройства необходимо дать соответствующие пояснения.
Задача 3
Физический объем сигнала и канала связи
Физическим объемом сигнала Vс называют произведение трех его физических характеристик: длительности сигнала Тс, ширины спектра Fc и динамического диапазона уровней сигнала / по мощности /Dc:
Vc = Tc Fc Dc;
Dc = 10 I g
В этом выражении Рмакс – максимальное (пиковое) значение мощности сигнала; Рмин – минимальное значение мощности сигнала.
Величина Vc чаще всего характеризует весь ансамбль используемых в данной системе связи сигналов. Иными словами, эта характеристика описывает сигнал как случайный процесс. В этом случае: Тс – это средняя длительность сигнала; Fc – ширина энергетического спектра, а Рмакс и Рмин при определении Dc для ансамбля с неограниченным числом реализаций представляют собой уровни мощности, которые соответственно превышаются и не превышаются с какой-то заданной малой вероятностью. Физический объем сигнала – весьма важная характеристика, позволяющая оценивать трудности, связанные с его передачей.
При наличии шумов в канале допустимый минимальный уровень мощности Рмин обычно определяется средней мощностью шумов в канале. Поэтому можно записать;
Dc = 10Ig
Максимальную мощность Рмакс иногда выражают через усредненную за достаточно большой интервал времени мощность сигнала Рс. В этом случае
Dc = 10Ig
Где П2 = - пикфактор сигнала по мощности. Эта величина зависит от статистики сигнала. Отношение средних мощностей сигнала и шума Рс/Рш часто называют просто сигнал/шум.
Аналогично физическому объему сигнала можно ввести характеристику, называемую физическим объемом канала
Vк = Тк Fк Dк.
Здесь Тк – время использования канала; Fr – полоса пропускаемых каналом частот; Gк – динамический диапазон уровней, пропускаемых каналом с допустимыми искажениями.
Для передачи сигнала, имеющего объем Vc, с достаточно высоким качеством необходимо выполнение неравенства
|
|
Vc ≤ Vк
При этом необходимо согласование сигнала и канала по всем трем параметрам, т.е.
Тс ≤ Тк, Fc ≤ Fк, Dc ≤ Dк.
Выполнение этих условий означает, что для обеспечения удовлетворительного качества при передаче сигналов требуется, чтобы объем сигнала «вписывался» в объем канала.
Естественно, что необходимо также согласование сигнала и канала в пределах общих интервалов времени, частот и уровней.
1. Канал связи с полосой Fк предполагается использовать в течение Тк секунд. В канале действует шум с равномерной спектральной плотностью мощности Gш, мВт/Гц. Какова предельная мощность сигнала, который может быть передан по данному каналу, если физический объем канала Vк.
Исходные данные для задачи в зависимости от предпоследней цифры шифра сведены в табл.3.
Таблица 3
Параметр | Предпоследняя цифра шифра | |||||||||
Fк кГц | ||||||||||
Тк, с | ||||||||||
Gш, мВт/Гц | 10-4 | 10-4 | 10-3 | 10-4 | 10-3 | 10-3 | 10-5 | 10-4 | 10-5 | 10-3 |
Vк | 106 | 106 | 107 | 105 | 106 | 106 | 105 | 106 | 104 | 105 |
2. Представить структурную схему системы передачи информации.
3. Привести классификацию и дать описание помех, возникающих в канале связи.