Июнь 18th, 2013
-f- 1 — V > f символах. С другой стороны, если минимальное расстояние меньше, чем 2t-\-l, то хотя бы в одном случае -кратная ошибка приведет к такому слову на выходе, которое по крайней мере столь же близко к одному из непередававшихся кодовых слов, как и к переданному кодовому слову. Наконец, аналогичными рассуждениями можно доказать, что декодирование, при котором исправляются все комбинации из t или меньшего числа ошибок и одновременно обнаруживаются все комбинации из d ила меньшего числа ошибок (d 2= г), возможно тогда и только тогда, когда минимальное расстояние между кодовыми словами равно t + d+l.Помимо того, что блоковые коды используются при решении задач теории связи, они находят применение также в нескольких других областях. Блоковые коды являются основой для распределения нагрузок при помощи переключательных матриц [47, 55, 203, 294], которые не только более эффективны, чем обычные системы адресов ячеек памяти, но и позволяют автоматически исправлять сбои отдельных компонент. По математической структуре они аналогичны некоторым планам статистических экспериментов [26, 183, 200]. Кроме того, предлагалось использовать эти коды в системах поиска документов [51], для уплотнения данных [16] и в специальных типах вычислительных машин.1.5. Древовидные кодыВ отличие от блоковых кодов коды, рассматриваемые в этом разделе, не связаны с разбиением на блоки информационной последовательности и последующей независимой их обработкой. Напротив, при древовидном кодировании каждой информационной последовательности ставится в соответствие (возможно, полубесконечная) кодовая последовательность. Правила, устанавливающие это соответствие, проще всего описать посредством древовидного графа. Пример двоичного древовидного графа приведен на фиг. 1.6. Вертикальные линии называются узлами, горизонтальные линии — ветвями. В общем случае каждая ветвь представляет собой
