Выбор кода и его параметров.

В передающем устройстве передаваемые команды управления (дискретные сообщения вида «включить» - «отключить») представляются в виде помехозащищенных кодов. По заданию 1 для передающего устройства рекомендуется использовать различные помехозащищенные коды (код Хэмминга, код на одно сочетание, код с удвоением элементов, код с повторением и др.)

а) Выбор кода Хэмминга

Код Хэмминга относится к корректирующим кодам. Он дает возможность обнаружить и исправлять одиночные искажения (τ=1 и s=1) или обнаруживать двойные искажения (τ=2) и исправлять одиночные искажения (s=1).

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

(1)

где τ – кратность обнаружения искажений;

s – кратность исправления искажений.

Минимальное кодовое расстояние для кода Хэмминга с обнаружением и исправлением одиночных искажений (τ=1 и s=1)

,

а с обнаружением двойных искажений (τ=2) и исправлением одиночных искажений (s=1).

Общее число комбинаций кода Хэмминга N при числе элементов в каждой комбинации n и d_m = 3 определяется следующей формулой:

(2)

При d_m = 4 и n общее число комбинаций кода Хэмминга N определяется формулой:

(3)

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

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

,

где N = 2^nо – количество используемых комбинаций кода Хэмминга;

N = 2ⁿ – максимальное возможное число комбинаций двоичного кода;

n₀ – число информационных элементов каждой комбинации кода Хэмминга;

n – общее число элементов каждой комбинации кода Хэмминга.

Пример. Определить общее число элементов в каждой комбинации n при N=20.

Для случая τ=1 и s=1 n определяется по формуле (2)

; n = 8

Для случая τ=2 и s=1 n определяется по формуле (3)

; n = 9

Рассмотрим, как составляются комбинации кода Хэмминга.

Сначала по заданным значениям кратности обнаружения τ и исправления s определяется минимальное кодовое расстояние d_m по формуле (1), а затем общее число элементов каждой комбинации n согласно формуле (2) или (3). Далее по формулам N = 2^nо и n=n₀+k определяется число информационных (n₀) и контрольных (к) элементов. После этого все элементы (разряды) комбинаций разбиваются на группы информационных и контрольных элементов. Для удобства обнаружения искаженного элемента группа контрольных элементов выбирается по закону 2^j, где j=0,1,2,3,4,…, т.е. в группу контрольных элементов будут входить 1,2,4,8,16-й …элементы. Здесь важным преимуществом является то, что каждый из этих элементов будет входить только в одну из проверяемых групп. В группу информационных элементов будут входить остальные элементы, на которых расписываются все комбинации числового кода 2^nо.

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

Таблица 1

В ходе проверки, если число единиц в проверяемых элементах четное, в соответствующем контрольном элементе записывается 0, если нечетное, записывается 1. После заполнения всех контрольных элементов получаем все комбинации кода.

Пример. Составить 35 комбинаций (N=35) кода Хэмминга с τ=1 и s=1.

Минимальное кодовое расстояние:

.

Число элементов n кодовой комбинации определяется по выражению (2)

;

, n = 9

Число информационных элементов по каждой комбинации определяется по выражению:

N = 2^nо; 35 = 2^nо; n₀ = 6

Число контрольных элементов:

к = n – n₀ = 9 – 6 = 3

В качестве контрольных элементов выбираем элементы 1,2,4, а в качестве информационных элементов 3,5,6,7,8,9. Сначала на информационных элементах (столбцах) 3,5,6,7,8,9 всех 35 кодовых комбинаций записываются 35 различных комбинаций из состава всех комбинаций числового кода

2^nо = 2⁶ = 64.

Затем заполняются контрольные элементы 1,2,4 всех 35 комбинаций (табл.2). Для заполнения контрольного элемента 1 первой комбинации (первой строки табл.2) проверяем четность числа единиц в элементах 3,5,7,9 (согласно табл.1). Число единиц в этих элементах нечетное:

,

поэтому в контрольном элементе 1 первой комбинации записывается 1. Здесь - знак сложения по модулю два.

Для заполнения контрольного элемента 2 первой комбинации (первой строки, табл.2) проверяется четность числа единиц элементов 3,6,7. В этих элементах число единиц также нечетное:

поэтому в контрольном элементе 2 первой комбинации записывается 1.

Число единиц в элементах 5,6,7 четное:

поэтому в контрольном элементе 4 первой комбинации записывается 0.

Таблица 2

Аналогичным образом заполняются контрольные элементы второй комбинации (второй строки табл.2). В контрольном элементе 1 второй комбинации записывается 1, так как число единиц в элементах 3,5,7 нечетное:

В контрольном элементе 2 второй комбинации записывается 0, так как число единиц в элементах 3,6,7 четное:

В контрольном элементе 4 второй комбинации записывается 1, так как число единиц в элементах 5,6,7 нечетное:

Аналогичным образом записываются остальные контрольные элементы по всем комбинациям табл.2. В результате получаем 35 различных комбинаций кода Хэмминга. Избыточность рассмотренного кода Хэмминга при n = 9 и n₀ = 6

Пример. Составить 35 комбинаций кода Хэмминга с τ=2 и s=1.

Минимальное кодовое расстояние:

.

Число элементов n кодовой комбинации определяется по выражению (3)

; n = 10

Число информационных элементов по каждой комбинации определяется из выражения:

N = 2^nо; 35 = 2^nо; n₀ = 6

Число контрольных элементов:

к = n – n₀ = 10 – 6 = 4

В качестве контрольных элементов выбираем элементы 1,2,4,10, а в качестве информационных элементов - элементы 3,5,6,7,8,9. Здесь все информационные элементы (3,5,6,7,8,9) и контрольные элементы 1,2,4 заполняются точно так же, как в предыдущем примере. Контрольный элемент 10 заполняется так, чтобы общее число единиц в каждой комбинации было четным (табл.3). С использованием контрольного элемента 10 создается дополнительное условие, по которому легко обнаруживаются также и двойные искажения (искажения в двух элементах).

Таблица 3

б) Выбор кода на одно сочетание

Общее количество комбинаций данного кода определяется числом сочетаний из n элементов по i:

Общее количество комбинаций N будет иметь максимальное значение, если при четном n принять и при нечетном n принять или .

Если, например, n = 5, то или .

Общее число комбинаций

или .

Часто при разработке телемеханических систем ставится задача определения числа элементов каждой комбинации (n) при заданном числе комбинаций N.

Пример. В системе телеуправления предусмотрена передача 15 команд. Требуется рассчитать число элементов, выбранных для этих 15 команд (кодовых комбинаций), кода на одно сочетание и составить их.

Число элементов кодовых комбинаций можно определить по выражению:

Если принять n = 5, то или

Полученное количество комбинаций 10 < 15, следовательно, выбором n = 5 нельзя получить все 15 комбинаций кода на одно сочетание.

Примем n = 6. Тогда и

Здесь 20 > 15, поэтому выбором n = 6 можно получить все 15 комбинаций кода на одно сочетание. Составим 15 комбинаций кода с n = 6 и i = 3 (табл.4)

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

Избыточность данного кода:

,

где - количество используемых комбинаций;

- максимальное возможное число комбинаций двоичного кода.

Таблица 4

в) Выбор кода с четным число единиц и нечетным числом единиц

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

Число элементов каждой комбинации кода можно определить по выражению

Комбинации кода с нечетным числом единиц составляются аналогично коду с четным числом единиц. Здесь из всех комбинаций кода 2ⁿ выбираются только те, которые содержат нечетное число единиц. Общее число комбинаций также определяется по формуле:

Пример. Определить число элементов каждой комбинации кода с четным числом единиц при общем числе комбинаций N = 15 и составить их.

Число элементов комбинации определяется по выражению:

Составим все 15 комбинаций кода с четным числом единиц (табл. 5).

Таблица 5

В данных кодах обнаруживаются одиночные и другие нечетные (3,5,7) искажения. Избыточность этих кодов:

г) Выбор кода с повторением

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

Пример. Общее число комбинаций кода с повторением N = 10. Рассчитать число элементов каждой комбинации такого кода и составить все 10 комбинаций.

Для двоичного кода общее число комбинаций определяется выражением

Отсюда .

Число элементов каждой комбинации кода с повторением будет

n_пов = 2·n = 2·4 = 8

Составим все 10 комбинаций кода с повторением при n_пов = 8 (табл. 6)

Таблица 6

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

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

д) Выбор кода с удвоением элементов

Этот код также строится на базе исходного двоичного кода. При этом каждый элемент исходной комбинации вида 0 представляется двумя элементами вида 01, а элемент вида 1 – двумя элементами вида 10. Так, например, исходная комбинация 101101 представляется в виде 100110100110. Так как парные элементы в комбинациях кода с удвоением элементов имеют только два вида «01» и «10», то появление в них наборов «00» и «11» будет свидетельствовать об искажении кода. Здесь не будут обнаруживаться только искажения вида 10 → 01 и 01 → 10 в парных элементах. Комбинация кода с удвоением элементов всегда содержит в два раза больше элементов, чем исходная комбинация, поэтому избыточность данного кода определяется выражением:

Пример. Рассчитать число элементов комбинации кода с удвоением элементов и составить эти комбинации, если общее число их равно 10 (N = 10).

Для обычного двоичного кода общее число комбинаций определяется выражением

. Отсюда .

Число элементов каждой комбинации кода с удвоением элементов при n_уд = 8 (табл.7)

Таблица 7

г) Выбор кода Грея

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

Для перехода от заданной комбинации двоичного кода к соответствующей комбинации кода Грея заданная комбинация суммируется по модулю 2 с такой же комбинацией, сдвинутой на один разряд вправо. Например, переход от заданной комбинации 1011 двоичного кода к соответствующей комбинации кода Грея осуществляется следующим образом:

101(1)

Аналогичным образом можно осуществлять переход от комбинации 1001:

100(1)

Пример. Общее число комбинаций кода Грея равно 15(N = 15).

Рассчитать число элементов каждой комбинации и составить их.

Общее число комбинаций кода Грея определяется следующим выражением:

.

Отсюда число элементов каждой комбинации кода Грея будет

.

Составим все 15 комбинаций (табл.8) кода Грея по вышеуказанному правилу.

Избыточность данного кода будет

Иногда с целью создания условия обнаружения искажений во всех комбинациях кода Грея вводится дополнительный n+1 элемент, который записывается нулем или единицей в зависимости от требуемого числа единиц в комбинации. В рассмотренном примере (см. табл.8) добавлением дополнительного пятого элемента в каждую комбинацию (пятого столбца) можно создать условия обнаружения искажений. При этом в пятом элементе каждой комбинации записывается 0, если число единиц в элементах 1,2,3,4 четное, и 1 – если единиц в элементах 1,2,3,4 нечетное.

Таблица 8 Таблица 9

В результате получим код с четным числом элементов в каждой комбинации (табл.9). Здесь любое нарушение четности числа единиц в комбинациях будет свидетельствовать о наличии искажения. Аналогичным образом можно образовать код с нечетным числом единиц.

Избыточность преобразованного кода

.

Не нашли, что искали? Воспользуйтесь поиском: