Cтраница 3
Таким образом, функция / ( х) - х3 подходит для построения нижних пяти строк проверочной матрицы SB двоичного кода с блоковой длиной 31 и 10 проверочными символами, исправляющего все двойные ошибки. Первые пять проверок задают сумму номеров ошибок; вторые пять проверок задают сумму кубов номеров ошибок. Процедура декодирования состоит из трех основных шагов: ( 1) производится проверка и вычисляются 8г и S3; ( 2) находится многочлен локаторов ошибок a ( z); ( 3) вычисляются взаимные величины для корней a ( z) и изменяются символы в соответствующих позициях полученного слова. [31]
Оператор вызова имени формирует слово косвенного обращения ( Indirect Reference Word - IRW) и помещает его в верхушку магазина. Из шести младших разрядов первого слога и восьми разрядов второго слога данного оператора образуется 14-разрядный адрес, который размещается в младших разрядах формируемого слога. К полученному слову приформировываются разряды тега, обозначающие, что это слово есть косвенная ссылка. Полученное слово помещается в верхушку стека. Таким образом, в магазине оказывается ссылка, состоящая из указания номера базы и относительного адреса элемента или ссылки на описатели ( дескрипторы) переменных и массивов. В дескрипторах указывается абсолютный адрес по памяти искомой величины или база ( адрес нулевого элемента) массива, к которому предполагается обращение. [32]
В первом случае в слове выбирается первая доступная для замещения совокупность символов DE в соответствии с заданными грамматиками. Вместо нее подставляются символы из некоторого правила. После этого полученное слово вновь просматривается, начиная слева, с целью поиска совокупности символов для замещения по правилам грамматики. [33]
Поскольку г - ( t -) t, большинство значений ( с, y ( v)) определяет, является ли а правильным или нет. Эта процедура применима к каждой позиции кода. Здесь видно преимущество циклических кодов, поскольку эта процедура, примененная к одной фиксированной позиции, продолжается циклическим сдвигом полученного слова. [34]
Идея этого метода заключается в следующем. Вводится в рассмотрение некоторая функция, определенная на множестве двоичных слов. Искомый код определяется как множество слов из В, на которых указанная функция принимает некоторое фиксированное значение. Функция подбирается таким образом, чтобы в результате любой одиночной ошибки значение функции изменялось и чтобы по этому изменению и, быть может, самому полученному слову можно было однозначно определить вид и место ошибки. Приводимые ниже доказательства также однотипны. Они состоят в описании декодирования, при котором в каждом кодовом слове будет исправлена любая одиночная ошибка рассматриваемого типа, если она произойдет. [35]
Замечательным примером таких высокоскоростных кодов являются коды с одной проверкой на четность, содержащие только один проверочный символ. Этот проверочный символ является суммой по модулю два п - 1 информационных символов. Двоичная сумма некоторого числа двоичных цифр равна 0 или 1 в соответствии с четностью или нечетностью числа единиц среди складываемых двоичных цифр. Поэтому общее число единиц ( включая проверочный символ) в каждом кодовом слове кода с одной проверкой на четность всегда четно. Если полученное слово содержит четное число единиц, то декодер должен декодировать его без изменений, а в противном случае слово не декодируется. Это правило неполного декодирования позволяет правильно декодировать только тогда, когда канал не исказил ни одного символа передаваемого блока. Одиночные ошибки ( или любое нечетное число ошибок) приводят к отказу от декодирования и тем самым обнаруживаются. Любое ненулевое четное число ошибок приводит к ошибке декодирования. [36]
Для построения линейных кодов для недвоичных каналов в множестве входных символов полезно ввести арифметическую структуру. Множество кодовых слов образует аддитивную группу; множество полученных слов с одним и тем же синдромом образует Смежный класс по этой подгруппе. Для фиксированного: полученного слова множество возможных векторов ошибок образует смежный класс, содержащий это слово. Задача декодера может быть, таким образом, сформулирована так: по заданному синдрому полученного слова найти наиболее вероятный вектор шума, лежащий в смежном классе слов с этим синдромом. [37]
Конечно, модифицируя алгоритм декодирования, часто можно изменить соотношения между отказами и ошибками декодирования. Сначала предположим, что если полученная последовательность содержит не более двух единиц, то она декодируется как нулевое кодовое слово. В противном случае она декодируется как единичное кодовое слово. Этот алгоритм декодирует каждое возможное полученное слово в одно из возможных кодовых слов; такое декодирование называется полным. В полных алгоритмах декодирования отказ от декодирования невозможен. [38]
В строках 49 и 50 осуществляется поиск в строке первого символа, не являющегося ни цифрой, ни буквой. Указатель р2 перемещается на этот символ. Теперь р1 и р2 указывают на начало и конец слова соответственно. Затем на основании данных о начале и длине полученное слово копируется в буферную переменную. [39]
В преобразуемой конструкции находят оболочку, внутри которой нет других оболочек. Выписывают все конструктивные элементы, из которых образована / С в произвольном порядке, а перед каждым из них пишут в лексикографическом порядке описания ветвей связей, для которых данный конструктивный элемент является связуемым объектом. Каждый фрагмент представляет собой слово в алфавите A jB jC [) D. Все выписанные фрагменты объединяют в лексикографическом порядке в одно слово, которое заключают в скобки (), после чего полученным словом заменяют в К конструкцию К вместе с одевающей ее оболочкой. [40]
Для построения линейных кодов для недвоичных каналов в множестве входных символов полезно ввести арифметическую структуру. Множество кодовых слов образует аддитивную группу; множество полученных слов с одним и тем же синдромом образует Смежный класс по этой подгруппе. Для фиксированного: полученного слова множество возможных векторов ошибок образует смежный класс, содержащий это слово. Задача декодера может быть, таким образом, сформулирована так: по заданному синдрому полученного слова найти наиболее вероятный вектор шума, лежащий в смежном классе слов с этим синдромом. [41]
Множество тг-мерных двоичных векторов с нулевым синдромом в точности совпадает с множеством кодовых слов. Таким образом, разность любой пары кодовых слов является кодовым словом. В общем случае, если х и у имеют один и тот же синдром ( не обязательно нулевой), то J x ( d y, Q № ( х - у) 0, и х - у является кодовым словом. Множество всех векторов, имеющих один и тот же синдром, называется смежным классом по подгруппе кодовых слов. Как только что показано, разность между любыми двумя векторами из одного и того же смежного класса является кодовым словом. Следовательно, число векторов в любом смежном классе равно числу 2fe кодовых слов. Возможными векторами ошибок являются слова из того смежного класса, которому принадлежит полученное слово. [42]