Материал: 6593

111

дать ему вопросов для того, чтобы определить сумму этих чисел, если на каждый вопрос спрашиваемый отвечает лишь «да» или «нет»?

4.2.11. Построить оптимальное множество кодовых слов для ансамбля X, заданного табл. 4.2.8.

Таблица 4.2.8

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

4.2.12. Сообщения гипотетического алфавита, заданного табл. 4.2.9, для передачи по двоичному каналу преобразуются кодером в последовательности кодовых символов 0 и 1 со сред-

Является ли полученный код оптимальным в статистическом смысле?

4.2.13. Радиотехническое устройство состоит из 5 блоков (А, Б, В, Г, Д). Блок А в среднем вых одит из строя 1 раз в 100 дней, блок Б – 1 раз в 25 дней, В – 1 раз в 5 дней, Г– один раз в 4 дня и блок Д – 1 раз в 2 дня. Контрольный прибор позволяет за одно измерение проверить работоспособность в целом любой комбинации блоков.

Как нужно проводить контроль, чтобы затратить на поиски

112

неисправного блока в среднем минимальное количество проверок? Найти это среднее значение.

4.2.14. Имеются 12 монет одного достоинства; 11 из них имеют одинаковый вес, а одна – фальшивая – отличается по весу от остальных (причем не известно, легче она или тяжелее настоящих). Каково наименьшее число взвешиваний на чашечных весах без гирь, которое позволяет обнаружить фальшивую монету и выяснить, легче она, чем остальные монеты, или тяжелее?

4.2.15. На кабельной линии длиной 20 км имеются 5 контрольных отводов, расположенных на расстоянии 1, 3, 5, 9 и 14 км от ее начала. Вероятность пробоя кабеля в любой точке линии одинакова. При осуществлении одной проверки можно установить исправность отрезка кабеля между любыми контрольными точками.

Как нужно проводить измерения, чтобы найти участок с поврежденным кабелем и произвести в среднем минимальное количество проверок?

4.2.16.Все буквы алфавита равновероятны, то есть избыточность отсутствует. При каком условии удастся закодировать этот алфавит двоичным кодом без избыточности?

4.2.17.Закодировать кодом Лемпела–Зива двоичную последовательность 0 0 0 0 1 0 0 0 0 0… и определить количество передаваемых двоичных символов, если используются трехразрядные номера комбинаций.

4.3 Кодирование в дискретном канале с шумом

Теоремы Шеннона о кодировании в дискретном канале с шумом. Дискретным каналом с шумом называется канал, в котором сигналы А(t) и В(t) (см. рис. 4.1.1) являются последовательностями символов, однозначная связь между входными и выходными сигналами отсутствует, и поэтому передача символов в канале сопровождается случайными ошибками.

Ответ на вопрос о возможности безошибочной передачи информации дается теоремами Шеннона о кодировании в дискретных каналах с шумом.

113

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

Обратная теорема. Если Н > С, то никакой код не сможет сделать вероятность ошибок сколь угодно малой и достигнуть ненадежности, меньшей чем Н-С.

Основной способ повышения помехоустойчивости системы передачи информации – это разумное введение избыточности в передаваемый сигнал А(t).

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

Пусть а1, а2, ... , аs – двоичные кодовые слова длиной в n символов каждое, соответствующие s буквам алфавита источника. Каждое кодовое слово можно формально рассматривать как вектор-строку, соответствующий некоторой точке в n-мерном пространстве.

Расстояние Хэмминга djk между двумя кодовыми словами аj и аk равно числу символов, в которых эти слова отличаются одно от другого.

Удобно вычислять расстояние между двумя кодовыми словами, пользуясь операцией суммирования по модулю 2. Правила cложения сведены в таблице 4.3.1, где

– знак операции суммирования по

эквивалентны.

Расстояние между двумя кодовыми словами можно теперь определить как количество единиц в кодовом слове, полученном при суммировании этих слов по модулю 2.

114

Наименьшее значение расстояния между словами в выбранной системе кодирования называется кодовым расстоянием

dкод.

Считают, что в канале произошла q-кратная ошибка, если кодовое слово на выходе канала отличается от кодового слова на его входе ровно в q символах (т.е. расстояние между этими словами-векторами равно q). Таким образом, вектор на выходе канала равен сумме по модулю 2 входного вектора и вектора ошибки.

Код позволяет обнаруживать любую ошибку кратности qо, если его кодовое расстояние удовлетворяет условию

Код позволяет исправлять любую ошибку кратности qи, если выполняется условие

Линейные блочные коды. Среди всех корректирующих кодов наибольшее применение нашли линейные блочные коды. Это – двоичный корректирующий (n,k)-код, удовлетворяющий следующим требованиям:

1) Все кодовые слова содержат по n символов, из которых k символов – информационные, а о стальные n-k символов – проверочные.

2) Сумма по модулю 2 любых двух кодовых слов снова дает кодовое слово, принадлежащее этому же коду.

Линейный блочный код код задается производящей матрицей G, имеющей k строк и n столбцов. Строки производящей матрицы должны быть линейно независимыми, т.е. сумма любых строк (по 2, по 3 и т.д. в любых комбинациях) не должна давать нулевое слово (состоящее из одних нулей).

Следующим этапом в построении линейного блочного кода является определение проверочной матрицы Н, имеющей r=n-k строк и n столбцов. Любой вектор-строка проверочной матрицы Н ортогонален любому вектору-строке производящей матрицы G, следовательно,

где HT – транспонированная матрица H.

115

Заметим, что два вектора u=u1,...,un и v=v1,...,vn являются, по определению, ортогональными, если

uv = u1v1 u2v2 ... unvn = 0 .

Работа кодера для (n,k)-кода заключается в том, что к поступающему на его вход k-разрядному вектору информационных символов x он должен добавить r проверочных символов. Правило образования кодового слова а определяется соотношением

a=xG. (4.3.4)

Умножив обе части этого выражения справа на HT и учитывая (4.3.3), получим другое соотношение, определяющее функции кодера

т.е. он должен добавлять r проверочных символов таким образом, чтобы любой из получаемых в итоге кодовых векторов а удовлетворял соотношению (4.3.5).

Один из способов декодирования принятого вектора b предусматривает вычисление r-разрядного исправляющего вектора (синдрома) с по правилу

с=bHT. (4.3.6)

Из формулы (4.3.5) следует, что значение синдрома определяется только вектором ошибки. Если с≠ 0, делают заключение о наличии ошибки (обнаружение ошибки). Так как различным ошибкам кратности qи, удовлетворяющей неравенству (4.3.2), соответствуют различные значения синдрома, то вычисленное значение синдрома с однозначно определяет положение символов, в которых произошли такие ошибки. Эти ошибки исправляются в декодере суммированием принятого вектора b с соответствующим вектором ошибок.

Основными элементами кодирующих и декодирующих устройств для систематических кодов являются сумматоры по модулю 2 и сдвигающие регистры. Сдвигающим регистром называют цепочку, состоящую из двоичных ячеек (в даль - нейшем они изображаются прямоугольниками), меняющую свое состояние в дискретные моменты времени (шагами). На каждом шаге двоичный символ, имеющийся на входе ячейки, перемеща-