Пример 9.4.1. Определим матрицу переходов состояний для (£/,к)-(1,3) кода. Код (1,3) имеет четыре состояния. Из рис. 9.4.4 получаем его матрицу переходов состояний, которая равна

1 О о"

£) =

О 1 О О О О

(9.4.3)

Важным параметром любого (d,K) кода является число последовательностей определённой длины, скажем w, которые удовлетворяют ограничениям (d, к) кода. Если н позволено расти, то число последовательностей N(n), удовлетворяющих ограничениям (d, к) кода, также растёт. Число информационных символов, которые можно однозначно представить посредством N(n) кодовых последовательностей, равно

где [xJ означает наибольшее целое, содержащееся в х. Тогда максимальная скорость кода Rc= kin.

Пропускная способность (d, к) кода определяется так

C{d,K) = \xm-\og,N{ti)

П-Ю) П

(9.4.4)

det (D-XI) = det

= Х->-Х-\ = 0. (9.4.6)

Ясно, что C{d,k) - это максимально возможная скорость, которую можно достичь при ограничениях на (d,K.). Шеннон (1948) показал, что пропускная способность C{d,k) определяется так:

Cid,k) = \og,X,, (9.4.5)

где - наибольшее вещественное собственное число матрицы состояний переходов D.

Пример 9.4.2. Определим пропускную способность {d, к) = (1, 3) кода. Используя матрицу состояний переходов из примера (9.4.1) для (1,3) кода имеем

-Х \ О О "

1 -А, 1 О 1 О -А. 1 1 О а -X

Максимальный вещественный корень этого полинома найден и равен Х - 1,4656. Следовательно, пропускная способность кода С(1,3)= logj Х =0,5515.

Пропускная способность id,K) кодов для 0<d<6 и 2<к<15 даны в табл. 9.4.1. Видим, что C(J,k)< для d>3 при любом к. Наиболее часто используемые коды для магнитной записи имеют d<2, следовательно, их скорость по крайней мере .

Теперь обратим наше внимание на конструирование некоторых кодов с ограниченным разбегом. В общем (d,K.) коды можно конструировать или как коды фиксированной длины, или как коды переменной длины. В коде фиксированной длины каждый символ или блок из к символов кодируется в блок из « ж символов.

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

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

Табл. 9.4.1. Пропускная способность C{d,k) как функция от параметров J и к

Пример 9.4.3. Синтезируем код с d = 0, к = 2 и длиной н = 3 и определим его эффективность. Из списка кодовых слов мы находим пять кодовых слов, удовлетворяющих ограничениям (О, 2) кода: (0 10), (0 11), (10 1), (110), (111). Мы можем выбрать любые четыре из этих кодовых слов и использовать их для кодирования пар кодовых символов (0 0), (0 1), (10), (11). Так мы получаем код со скоростью к/п = 2/3, который удовлетворяет условиям (О, 2) кода-Код фиксированной длины в этом примере не очень эффективен. Его пропускная способность С(0, 2) - 0,8791, так что этот код имеет эффективность

эффективность =

£ -

= 0,76.

C(d,k) 0,8791

Конечно, лучшие (О, 2) коды можно сконструировать увеличением длины блока п. В следующем примере, мы не накладываем ограничение на максимальное простирание нулей.

Пример 9.4.4. Сконструируем код длиной и = 5 с параметрами d = \, к = оо. В этом случае, мы не накладываем ограничения на число последовательных нулей. Для конструирования кода мы выберем из 32 возможных кодовых слов те. которые удовлетворяют ограничению d = 1. Имеется восемь таких кодовых слов, что подразумевает, что мы можем кодировать три информационных символа с каждым кодовым словом. Код дан в таблице 9.4.2. Заметим, что первый символа каждого кодового слова есть О, в то время как последний символ может быть или О, или 1. Следовательно, когда эти кодовые слова каскадно соединяются, ограничение d = 1 удовлетворяется. Этот код имеет скорость R=3/5. Если её сопоставить с пропускной способностью

С(1, оо) = 0,6942, полученной из таблицы 9.4.1, то эффективность кода равна 0,864, что вполне приемлемо.

Таблица 9.4.2. Код с фиксированной длиной, d=\, к - сю

Входные символы данных Выходные кодированные последовательности

Метод конструирования кодов, описанный выше в двух примерах, приводит к кодам (с/, к) фиксированной длины, которые независимы по состояниям. Под независимостью

состояний мы имеем в виду, что кодовые слова кода фиксированной длины могут быть каскадно объединены без нарушения ограничений на (d,K) коды. В общем, когда d велико, коды (d,K) фиксированной длины с независимостью по состояниям требуют большую длину блока символов. Возможны более простые (короткой длины) коды, в которых допустима зависимость состояний и переменная длина кодовых слов. Ниже мы рассмотрим коды, для которых как длина входных блоков на кодер, так и выходные блоки могут иметь переменную длину. Для однозначного декодирования кодовых слов в приёмнике коды переменной длины должны удовлетворять префиксному условию, описанному в главе 3.

Пример 9.4.5- Очень простым уникальным декодируемым кодом переменной длины с параметрами - О, к = 2 является код

1010

11->11.

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

Пример 9.4.6. Сконструируем код (2, 7) с переменными размерами блока. Это несложный код. Мы выбрали этот пример потому, что код (2, 7) широко известен в технике ПЭВМ для многих дисковых систем хранения информации. Код иллюстрируется в таблице 9.4.3. Мы видим, что входные блоки данных из 2, 3, и 4 символов отображаются в выходные блоки данных из 4,6 и 8 символов, соответственно. Следовательно скорость кода =. 1/2. Поскольку это скорость кода для всех кодовых слов, код называется кодом с фиксированной скоростью. Это код имеет эффективность 0,5/0,5174 = 0,966. Заметим, что этот код удовлетворяет префиксному условию.

Другой код, который широко используется в магнитной записи - это код {d,K.) = (1, 3) со скоростью 1/2, иллюстрированный табл. 9.4.4. Видим, что когда информационный входной символ О, то первый выходной символ 1, если предшествующий входной символ был О, или первый выходной символ О, если предшествующий входной символ был 1, а второй выходной символ 0.