Задача 2. Коды Хемминга. Функциональные схемы кодирующих и декодирующих устройств линейных кодов

Коды Хемминга. Функциональные схемы кодирующих и декодирующих устройств линейных кодов

1. Построить код Хемминга, взяв в качестве исходной кодовой комбинации двоичное число, полученное из двух последних цифр шифра студента. Определить вероятность ошибочного приема полученной комбинации кода Хемминга и вероятность появления необнаруживаемой ошибки.

2. Дать общую характеристику и классификацию корректирующих кодов.

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

4. Изложить функциональную схему кодирующего устройства кода Хемминга.

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

Любой корректирующий код содержит n элементов, из которых k информационных и r проверочных (информации не несут). Тогда n = k+r.

Код Хемминга относится к блочным разделимым систематическим корректирующим кодам. Его проверочные элементы формируются путем суммирования по модулю два (проверка на четность).

Длину кодовой комбинации n кода Хемминга при заданном числе информационных элементов k можно определить из неравенства

2^k ≤

Рассмотрим принцип построения кодовой комбинации кода Хемминга, если шифр студент 87-ЭТ-7.

Учитывая, что в шифре содержится только одна цифра 7, к ней необходимо добавить цифры 1 и 0. В этом случае шифр будет иметь вид 87-ЭТ-107.

Выразим полученное число в двоичной форме счисления путем последовательного деления числа 107 на 2:

Так как последний остаток есть коэффициент при основании системы с наивысшей степенью, то число 107 в двоичной системе счисления записывается в виде 11010011 (смотри числители остатков). Следовательно, исходная кодовая комбинация будет иметь семь элементов (k=7).

Определим число проверочных элементов из неравенства

2⁷

Отсюда n = 11, r = 4. Следовательно, кодовая комбинация будет содержать 11 элементов, из которых 7 информационных, а 4 проверочных.

Определим позиции проверочных элементов в кодовой комбинации. Для этого запишем номера позиций кодовой комбинации в двоичной системе счисления – табл.2.

Таблица 2

N позиции	Двоичное число

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

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

S₁ = α₁ α₃ α₅ α₇ α₉ α₁₁

Проверочным элементом является первая позиция кодовой комбинации, е ее значение можно определить из выражения

α₁ = α₃ α₅ α₇ α₉ α₁₁

Результат второй проверки определяет второй разряд двоичного числа. Из табл.2 находим все номера позиций, имеющие единицу во втором разряде:

S₂ = α₂ α₃ α₆ α₇ α₁₀ α₁₁

Проверочным элементом является вторая позиция:

α₂ = α₃ α₆ α₇ α₁₀ α₁₁

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

S₃ = α₄ α₅ α₆ α₇ α₄ = α₅ α₆ α₇

S₄ = α₈ α₉ α₁₀ α₁₁ α₈ = α₉ α₁₀ α₁₁

Cледовательно, проверочными элементами являются 1-я, 2-я, 4-я, 8-я позиции, а остальные – информационными. Тогда информационные элементы будут иметь значения:

α₃ = 1, α₅ = 1, α₆ = 0, α₇ = 1, α₉ = 0, α₁₀ = 1, α₁₁ = 1.

Определим значения проверочных элементов:

α₁ = 1 1 1 0 1 = 0 α₂ = 1 0 1 1 1= 0;

α₄= 1 0 1 = 0; α₈ = 0 1 1 = 0.

В результате получим комбинацию кода Хемминга 00101010011, которая будет передана в канал связи.

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

Задача 3

Физический объем сигнала и канала связи

Физическим объемом сигнала V_с называют произведение трех его физических характеристик: длительности сигнала Т_с, ширины спектра F_c и динамического диапазона уровней сигнала / по мощности /D_c:

V_c = T_c F_c D_c;

D_c = 10 I g

В этом выражении Р_макс – максимальное (пиковое) значение мощности сигнала; Р_мин – минимальное значение мощности сигнала.

Величина V_c чаще всего характеризует весь ансамбль используемых в данной системе связи сигналов. Иными словами, эта характеристика описывает сигнал как случайный процесс. В этом случае: Т_с – это средняя длительность сигнала; F_c – ширина энергетического спектра, а Р_макс и Р_мин при определении D_c для ансамбля с неограниченным числом реализаций представляют собой уровни мощности, которые соответственно превышаются и не превышаются с какой-то заданной малой вероятностью. Физический объем сигнала – весьма важная характеристика, позволяющая оценивать трудности, связанные с его передачей.

При наличии шумов в канале допустимый минимальный уровень мощности Р_мин обычно определяется средней мощностью шумов в канале. Поэтому можно записать;

D_c = 10Ig

Максимальную мощность Р_макс иногда выражают через усредненную за достаточно большой интервал времени мощность сигнала Р_с. В этом случае

D_c = 10Ig

Где П² = - пикфактор сигнала по мощности. Эта величина зависит от статистики сигнала. Отношение средних мощностей сигнала и шума Р_с/Р_ш часто называют просто сигнал/шум.

Аналогично физическому объему сигнала можно ввести характеристику, называемую физическим объемом канала

V_к = Т_к F_к D_к.

Здесь Т_к – время использования канала; F_r – полоса пропускаемых каналом частот; G_к – динамический диапазон уровней, пропускаемых каналом с допустимыми искажениями.

Для передачи сигнала, имеющего объем V_c, с достаточно высоким качеством необходимо выполнение неравенства

V_c ≤ V_к

При этом необходимо согласование сигнала и канала по всем трем параметрам, т.е.

Т_с≤ Т_к, F_c ≤ F_к, D_c ≤ 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_к	10⁶	10⁶	10⁷	10⁵	10⁶	10⁶	10⁵	10⁶	10⁴	10⁵