Другие используемые коды

Часто коды рассматривают, как упорядоченные наборы кодовых слов: K={A₁, A₂, … A_n}, в которых порядок задается по определенному принципу. Такие коды называют упорядоченными. Самый распространенный принцип упорядочения лексикографический, то есть в соответствии с порядком символов в алфавите (также как слова упорядочиваются в словарях). Коды с лексикографическим упорядочением называются прямыми. К прямым кодам относится упоминавшийся ранее код Трисиме. Если символы кода рассматривать как цифры, то порядок слов в прямом коде соответствует порядку чисел в позиционной системе счисления.

Следующая таблица представляет примеры упорядоченных кодов (взята из книги Ф.Бауэр, Г.Гооз «Информатика», стр. 44):

Задача 13. Чему равны избыточности кодов в указанной выше таблице, если считать передаваемые в сообщениях десятичные цифры равновероятными?

Назовем последовательность из 0 и 1 длины не более 2ⁿ n-регулярной, если никакие ее две подпоследовательности, идущих подряд символов, длины nне совпадают. Например, последовательность 00011101 является 3-регулярной, так как все тройки, стоящих рядом символов, отличаются друг от друга. (Двоичная последовательность длины большей, чем 2ⁿ, не может быть n-регулярной. Объясните, почему.)

Говорят, последовательность является циклической, если ее рассматривать как бы замкнутой по кругу, то есть продолжением ее является она же сама от своего начала. Например, если последовательность 00011101рассматривать как циклическую, то к шести ее тройкам добавятся еще две тройки: 010 и 100. Теперь все восемь троек оказываются различными.

Двоичная последовательность длины не более 2ⁿ называется циклически n-регулярной,

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

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

Циклический код порядкаn можно получить в виде упорядоченного ряда кодовых слов, двигаясь по циклически n-регулярной последовательности с шагом в один символ и выбирая через «смотровое окошко» слова длины n. Например, двигаясь слева направо по последовательности 00011101и выбирая слова длины3, мы получаем следующий циклический код порядка 3:

{ 000, 001, 011, 111, 110, 101, 010, 100 }.

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

Если обойти вершины куба по-другому пути, это приведет к другому варианту кода Грея.

Если имеются два кода Грея: K₁ порядка n и другой K₂ порядка m, то можно построить код Грея Kпорядка n+mследующим образом. Строится клетчатый квадрат размера n·m. Слева напротив каждой строки выписываются nкодовых слов кода K₁, а над столбцами квадрата выписываются mкодовых слов кода K₂, Каждой клетке квадрата ставится в соответствие кодовое слово длины n+m, левая часть которого берется из строки этой клетки (слева), а правая часть – из столбца этой клетки (сверху). Код Kпорядка n+mполучается обходом клеток квадрата так, чтобы переход от клетки к соседней клетке происходил или по горизонтали, или по вертикали.

Покажем это на примере построения кода Грея порядка 4. На следующем рисунке изображен клетчатый квадрат размера 4·4

Показанный на рисунке обход клеток квадрата приводит к следующему коду Грея:

{0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101 }.

Этот код как раз соответствует коду Грея, показанному в представленной выше таблице.

Пусть задано двоичное слово длины n A=α₁α₂…α_n . Двоичное слово B=β₁β₂…β_nназовем производной слова A, если β_i=0в случае α_i= α_i-1 и β_i=1в противном случае, полагая α₀=0. Короче это можно записать так: β_i= α_i+α_i-1 , где сумма берется по модулю 2. Например, для слова 1010101 производным словом будет 1111111, так как в исходном слове никакие два рядом стоящих бита не равны и слово начинается с 1. Для слова 0000000производным словом будет оно же само, так как все рядом стоящие биты равны и слово начинается с 0.

Задача 16. Пусть A=α₁α₂…α_n- двоичное слово, а B=β₁β₂…β_n – его производное слово. Покажите, что восстановить слово A, если известно его производное слово Bможно по правилу: α_i= β_i+ α_i-1 , где α₀=0.

Пусть заданы равномерные двоичные коды порядкаn K={A₁, A₂, … A_m}и K’={B₁, B₂, … B_m}. Код K’называется производным кода K, если B_i (i-ое кодовое слово K’)является производным словом A_i (i-ого кодового слова K).

Задача 17. Доказать, что производный код прямого кода является кодом Грея.

Задача 18. Покажите, что у кода, производного коду Грея, почти все пары соседних кодовых слов находятся на расстоянии 2, кроме некоторых исключений (каких?).

Пусть A - двоичное кодовое слово, обозначим Ā слово, полученное из A заменой всех 0 на 1, а всех 1 на 0. Назовем двоичное кодовое слово четным, если в нем четное число единиц, и нечетным - в противном случае.

Пусть задан двоичный код порядкаn K={A₁, A₂, … A_m}. Образуем новый код порядка2n : K_B={B₁, B₂, … B_m}, где B_i = A_iA_i , если A_i- четный код, и B_i =A_iĀ_i , если A_i– нечетный ( здесь A_iA_i и A_iĀ_i- кодовые слова длины 2n, полученные приписыванием одного слова к другому). Полученный таким образом код называется кодом Бауэра.

Теорема. Ширина кода Бауэра, полученного из кода порядкаn, равна 4, еслиn≥4, и равнаn, еслиn<4(то есть ширина кода Бауэра равнаmin(4,n)).

Лемма 1. ρ(A_i, A_j)≥2, если оба словаA_iиA_jчетны, или оба словаA_iиA_jнечетны.

Лемма 2. ρ(A_iA_j, A_kA_l) = ρ(A_i, A_k)+ρ(A_j, A_l).

Лемма 3.Если словаA_iиA_jдлины n, то ρ(A_i, A_j)+ ρ(A_i, Ā_j) = n.

Доказательство теоремы.Пусть B_iи B_j- два кодовых слова кода Бауэра. Если A_iиA_jоба четны, то ρ(B_i, B_j) = ρ(A_iA_i, A_jA_j) = ρ(A_i, A_j)+ ρ(A_i, A_j) ≥ 2 + 2 = 4(по указанным выше леммам 1 и 2). Если A_iиA_jоба нечетны, то ρ(B_i, B_j) = ρ(A_iĀ_i, A_jĀ_j) = ρ(A_i, A_j)+ ρ(Ā_i, Ā_j) ≥ 2 + 2 = 4(так какĀ_iи Ā_j оба четны или оба нечетны).

Пусть теперь A_iиA_jразной четности, например,A_i- четное слово, а A_j- нечетное.Тогда ρ(B_i, B_j) = ρ(A_iA_i, A_jĀ_j) = ρ(A_i, A_j)+ ρ(A_i, Ā_j) = n(по леммам 2 и 3). Теорема доказана.

Из доказанной теоремы следует, что код Бауэра, порядок которого ≥ 8, является кодом с обнаружением двух ошибок.

Задача 19. Является ли код, состоящий из следующих четырех слов: {0000, 0110, 1001, 1111}, кодом Бауэра.

Задача 20. Составить код Бауэра порядка 8.