Cтраница 2
Если г-я буква переданного слова а отличается от г-й буквы полученного слова ( 3, то говорят, что произошла ошибка в г-м разряде. Если полученное слово отличается от переданного в t разрядах, то говорят, что произошло t ошибок. Ясно, что число ошибок, имевших место при передаче, равно расстоянию Хэмминга между переданным и принятым словами. [16]
Совершенный код легко декодировать: каждому полученному слову однозначно ставится в соответствие ближайшее кодовое. Чисел т, п и k ( I k - -), удовлетворяющих условию совершенности кода очень мало. [17]
Запись нормального алгоритма можно превратить в слово, выписывая его формулы одну за другой и разделяя их буквами К. Теперь можно придумать некоторый прием кодирования, в результате которого полученное слово станет словом в А, конечно при условии, что алфавит А состоит не менее, чем из двух букв. Этот способ кодирования, например, может быть следующим. [18]
В общем случае если предположить, что произошло t и ошибок, то, используя разложение в ряд для производящей функции Д2), можно получить систему уравнений относительно и неизвестных коэффициентов многочленов U и F. Эта система может не иметь решения ( что случится, когда полученное слово лежит в смежном классе, все слова которого имеют вес i и), может иметь несколько допустимых решений или единственное решение. [19]
Постоянная составляющая запасается в программе в виде некоторой константы, а переменная составляющая вычисляется каждый раз наново по фактическим значениям индексных выражений ( индексов) в виде условно-целого числа. Затем перед выполнением переменной команды производится сложение этих составляющих и засылка полученного слова на место данной переменной команды. [20]
Порядок выполнения подстановок полностью определяется после этого условиями а, б, и в. Процесс выполнения подстановок заканчивается лишь тогда, когда ни одна из подстановок схемы не применима к полученному слову или когда выполнена ( первый раз) какая-либо заключительная подстановка. [21]
Нормальные алгоритмы принято задавать упорядоченным множеством подстановок всех операторов данного алгоритма, называемым схемой алгоритма. Процесс выполнения подстановок заканчивается лишь тогда, когда ни одна из подстановок схемы не применима к полученному слову или когда выполнена ( первый раз) какая-либо заключительная подстановка. [22]
Формула (16.16), полученная Мак-Вильяме [1963], определ; вероятность отказа от декодирования в случае, когда число t мень половины минимального расстояния кода. Случай t 0 соотв ствует очень неполному алгоритму декодирования, который де дирует лишь тогда; когда полученное слово является кодов. [23]
Ясно, что это правило декодирования позволяет декодировать правильно во всех случаях, когда шум в канале искажает меньше-половины символов в каждом блоке. Если шум в канале искажает более половины символов некоторого блока, то в декодере произойдет ошибка декодирования: он неверно декодирует полученное слово. При редких ошибках в канале вероятность отказа или ошибки декодирования для кода с повторением с большой блоковой длиной, очевидно, очень мала. [24]
Обнаружение источника прерывания в простейшем случае сводится к опросу флагов задействованных внешних устройств со счетом числа пройденных звеньев такой цепочки; выход в следующий блок осуществляется при обнаружении первого же флага, установленного в единичное состояние. Если этот флаг оказался в единичном состоянии считывается все слово флагов и дальнейшая программа организуется на основе какого-либо цикла поразрядного анализа полученного слова. Очевидно, последовательность опроса флагов в этом случае определяется положением разряда, закрепленного за каждым из них. Иногда таким априорным ранжированием и завершается установление приоритетов для потока задач, однако система оказывается более гибкой, если приоритет задачи рассматривается как ее отдельная дополнительная характеристика. [25]
Нормальные алгоритмы принято задавать упорядоченным мног жеством подстановок всех операторов данного алгоритма, называемым схемой алгоритма. При этом обычные подстановки записываются, как и в обобщенных алгоритмах, в виде двух слов, соединенных стрелкой ( PI-рг), а заключительные подстановки обозначаются стрелкой с точкой ( pi - - Pz - Процесс выполнения подстановок заканчивается лишь тогда, когда ни одна из подстановок схе - - мы не применима к полученному слову или когда выполнена ( первый раз) какая-либо заключительная подстановка. [26]
Оператор вызова имени формирует слово косвенного обращения ( Indirect Reference Word - IRW) и помещает его в верхушку магазина. Из шести младших разрядов первого слога и восьми разрядов второго слога данного оператора образуется 14-разрядный адрес, который размещается в младших разрядах формируемого слога. К полученному слову приформировываются разряды тега, обозначающие, что это слово есть косвенная ссылка. Полученное слово помещается в верхушку стека. Таким образом, в магазине оказывается ссылка, состоящая из указания номера базы и относительного адреса элемента или ссылки на описатели ( дескрипторы) переменных и массивов. В дескрипторах указывается абсолютный адрес по памяти искомой величины или база ( адрес нулевого элемента) массива, к которому предполагается обращение. [27]
При таком декодировании декодер на базе полученного слова составляет список всех возможных переданных кодовых слов в порядке убывания их апостериорных вероятностей. Если переданное слово появится в любом месте этого списка, то декодер правильно примет его. Ошибка декодирования произойдет только тогда, когда фактически переданное слово не содержится в списке. [28]
Если же произошло больше чем t ошибок, то возможны многие другие исходы. Возможно также, что алгоритм 7.4 завершится допустимым многочленом локаторов ошибок и допустимым многочленом значений ошибок, соответствующими некоторому вектору ошибок с весом г. В этих случаях декодер без труда завершает шаги 10.153 и 10.154 процедуры декодирования и неправильно исправляет происшедшие по его мнению ошибки. Хотя в этой ситуации декодер ошибается, порицать его за эту ошибку нельзя, так как для полученного слова неправильно найденный вектор ошибок является более вероятным, чем фактический вектор ошибок с бблыпим весом. [29]
Отказ от декодирования, напротив, может привести лишь к игнорированию команды. В такого рода приложениях предпочтительным является алгоритм о значительной неполнотой декодирования, который умышленно отказывается от декодирования любого достаточно сомнительного полученного слова. [30]