Cтраница 3
Например, для построения кода, обнаруживающего все двойные и исправляющего все одиночные ошибки, необходимо, чтобы разрешенные комбинации отличались друг от друга не менее чем в четырех разрядах. [31]
Существует несколько систем построения кодов: порядковая, серийная, поразрядная, система повторения и комбинированная. [32]
Один из методов построения кодов, обеспечивающих защиту от одиночных искажений, состоит в использовании только кодовых слов с четным или нечетным числом единиц. [33]
Постановка второй задачи - построения кода, приводящего к наиболее простой логической пасти устройства, принадлежит Дж. Предложенный им подход сводится к декомпозиции - разбиению исходного автомата на блоки; при этом состояния элементов памяти зависят только от выходов элементов памяти того же блока, что приводит к логическим функциям от меньшего числа переменных. Работа [112] посвящена одновременному решению обеих указанных задач кодирования состояний. В работе [113] впервые поставлена третья задача кодирования - построение кода, приводящего к структуре, устойчивой к d - оптибкам элементов памяти. Эта задача рассмотрена в разделе Теория структурной надежности настоящей статьи; здесь мы упомянем лишь о работах [114], в которых предложены методы одновременного решения первой и третьей задач. Оригинальное решение вопроса размещения состояний нашли в монографии [115], авторам которой был разработан метод синтеза асинхронных релейных устройств, основанный на реализации каждой внутренней переменной в виде инерционной подсхемы, реализующей как саму внутреннюю переменную, так и все переходы к нет. Этот метод дает размещение, обеспечивающее в некоторой степени простоту структуры и облегчающее устранение недопустимых состязаний. К вопросам абстрактного синтеза по своему содержанию ( но не по методам) примыкает группа работ, связанных с построением блочных структур из автоматов. Помимо упомянутых работ [78, 79] по блочному синтезу советским авторам принадлежит ряд важных результатов по исследованию проблемы полноты для различных базисов ( наборов) автоматов. В [116] доказана полнота одной системы автоматов без обратных связей; в [117] сформулированы условия полноты для автоматов Мура; п [118] доказана алгоритмическая неразрешимость проблемы полноты для произвольных систем автоматов, а в [119] даны асимптотические оценки числа неизоморфных автоматов. [34]
Таким образом, задача построения кода с заданной корректирующей способностью сводится к обеспечению необходимого кодового расстояния путем введения избыточности. При этом желательно, чтобы число используемых проверочных символов было минимальным. К сожалению, задача определения минимального числа проверочных символов, необходимых для обеспечения заданного кодового расстояния, в общем виде не решена. [35]
Итак, видно, что построение помехоустойчивого кода ( а код с обнаружением ошибки является простейшим типом такого кода) связано с недоиспользованием кодовых комбинаций, приводящим к так называемой избыточности. Избыточность означает, что из исходных символов можно построить больше комбинаций, чем их применено в данном коде. [36]
Так, например, для построения тп-ичных кодов Шеннона - Фано надо лишь разбивать группы символов не на две, а на т частей по возможности близкой вероятности, а для построения т-ично-го кода Хафмана надо использовать операцию сжатия алфавита, при которой каждый раз сливаются не две, а т букв исходного алфавита, имеющих наименьшие вероятности. [37]
В этом разделе рассматривается метод построения кода для источника стационарного гауссовского случайного процесса. Метод приводит к относительно простой реализации, а его основная информационная характеристика - скорость кодирования - относительно мало отличается от е-эитропии. [38]
Нетрудно убедиться в принципиальной возможности построения асимптотически оптимального счетного кода. [39]
Возникающие здесь задачи состоят в построении кода в В, имеющего максимальную достоверность среди кодов заданной мощности, и в оценке его достоверности. [40]
В следующем параграфе будет описан метод построения кодов, из которого следует, что верхняя оценка в ( 6), а значит, и верхняя оценка в ( 3), указывает порядок роста функции т ( п, 2s l) при фиксированном и и-оо. С другой стороны, если число s растет достаточно быстро ( например, линейно) с ростом п, то верхняя оценка в ( 3) может быть существенно улучшена с помощью некоторого обобщения метода заполнения. [41]
Максимальное число, которое используется при построении кода ( обозначим его kmax), получается больше, чем k, но это превышение невелико. [42]
Поскольку матрица-дополнение содержит всю информацию о правилах построения кода, то систематический код с заданными свойствами можно синтезировать путем построения соответствующей матрицы-дополнения. [43]
Кроме того, теория информации изучает методы построения кодов, обладающих полезными свойствами. [44]
Рассмотрим вторую сторону вопроса, определяющую оптимальность построения кода, - задачу запоминания знаков оператором в зависимости от кодирования информации. [45]