Основы бортовых вычислительных машин
 Скачать 3.2 Mb.
|
|
x x − + + − = , где { } 0,1 i x ∈ По форме внесения избыточности различают систематические и несистематические коды. В систематических кодах символы инфор- мационной последовательности входят без изменения в передаваемое сообщение, занимая в нем отведенные им позиции, а кодирование сводится к внесению в передаваемое сообщение дополнительных 239 (избыточных) символов, связанных определенной зависимостью с символами информационной последовательности. В явном виде они в передаваемое сообщение не входят, а могут быть установлены по из- вестным зависимостям, связывающим их с символами передаваемого сообщения. По способу кодирования различают блочные и непрерывные ко- ды. При блочном кодировании информационная последовательность разбивается на блоки символов ( ) 1 2 , ,..., k b b b фиксированной длины k , каждому из которых ставится в соответствие определенная комби- нация символов алфавита канала ( ) 1 2 , ,..., n β β β , называемого кодо- вым словом. Код при блочном кодировании определяет закон форми- рования кодового слова, отвечающего данному блоку информацион- ных символов. В случае систематического блочного кода кодовое слово, отве- чающее блоку информационных символов ( ) 1 2 , ,..., k b b b , может быть представлено в виде ( ) 1 2 1 , ,..., , , ,..., k k k n b b b β β β + , где 1 ,..., k n β β + - из- быточные символы. Блочный код, приводящий в соответствие блоку информационных символов длиной k кодовое слово длиной n , будем обозначать ( ) , k n . Избыточные символы не несут дополнительной информации об источнике сообщения (они однозначно определяются информационными символами 1 2 , ,..., k b b b ), Поэтому кодовое слово несет то же количество полезной информации, что и соответствую- щий блок информационных символов. При безызбыточности входно- го сообщения блок из k информационных символов (а значит, и ко- довое слово) несет количество информации 2 log Н k m = , где m - объем алфавита источника. Максимальное количество информации, которое может содер- жать слово из n символов канала при том же объеме алфавита m , равно max 2 log Н n m = Поэтому избыточность кода ( ) , k n 2 max 2 log 1 1 log и k m Н n k r Н n m n n ρ − = − = − = = , где r n k = − - число избыточных символов, вносимых при кодирова- нии. При непрерывном кодировании каждый символ передаваемого сообщения определяется рекуррентными соотношениями, 240 связывающими его с соответствующими символами информационной последовательности: 1 , (mod ), 0,1,..., 1 S i j j i q C b m j l ν ν ν β = + =− = = − ∑ (6.4) Значение правой части выражения (6.4) определяется по моду- лю m для того, чтобы полученные значения символов , i j β принадле- жали алфавиту канала, т.е. принимали одно из значений 0, 1, ..., m -1. Соотношение (6.1) на i - м шаге кодирования группе символов входной последовательности 1 ,..., ,..., i q i i s b b b − + − ставит в соответствие l символов кодовой последовательности ,0 , 1 ,..., i i l β β − ; на ( i +1)- m шаге группе символов 1 1 ,..., ,..., i q i i s b b b − + + + , смещенной на одну пози- цию, ставит в соответствие следующие l символов кодовой последо- вательности 1,0 1, 1 ,..., i i l β β + + − и т.д. Таким образом, на каждый символ информационной последовательности приходится l символов пере- даваемой кодовой последовательности, что соответствует избыточно- сти кода ( ) 1 / и l l ρ = − . Правая часть соотношения (6.4) представляет как бы свертку соответствующего участка информационной последо- вательности, поэтому коды и называют сверточными. Непрерывные (сверточные) коды могут быть как систематиче- скими, так и несистематическими. Систематические сверточные коды получаются в частном случае, когда для одного из значений индекса j (например, j = 0) коэффициенты в формуле (6.4) принимают значе- ния 0 0, при 0, 1, при 0 C ν ν ν ≠ = = и соответственно 0 i i b β = . В этом случае передаваемая последова- тельность имеет вид ,1 , 1 1 1,1 1, 1 ... , ,..., , , ,..., ,... i i i l i i i l b b β β β β − + + + + 6.3.2 Коды, контролирующие ошибки Одним из наиболее широко распространенных способов контро- ля передачи, хранения и обработки цифровой информации, в том чис- ле и в бортовых ЭВМ, является контроль по модулю. При контроле 241 по модулю используется избыточная информация, представляемая дополнительными разрядами в информационном слове. Количество дополнительных разрядов определяется значением модуля, по кото- рому производится контроль. Суть метода заключается в определении и анализе по некоторым правилам контрольных кодов, представляющих собой наименьшие остатки от деления на модуль самих чисел (числовой контроль) или суммы их цифр (цифровой контроль). В первом случае контрольные разряды определяются из соот- ношения: m х ост m α = , где x - контролируемое число; m α - наименьший остаток от деления числа x на модуль m . Например, при контроле по модулю 2 для числа x = 1001 полу- чаем 2 1001 1 10 ост α = = В этом случае избыточный код имеет значение 2 х = 1001 1 контрольный разряд. Очевидно, все нечетные числа будут иметь контрольный разряд равный единице, а четные - нулю. Контроль в этом случае сводится к следующим действиям: формированию контрольного разряда на пе- редающей позиции; передаче избыточного кода; проверке сформиро- ванного по тем же правилам контрольного разряда на приемной по- зиции с полученным по каналу контрольным разрядом. В случае числового контроля по модулю два ошибка не будет обнаружена в том случае, если в результате искажений четное число останется четным, а нечетное - нечетным. Вероятность такого собы- тия близка к 0,5. Чем больше значение модуля, тем больше число контрольных разрядов добавляется в передаваемое сообщение. В то же время больше вероятность обнаружения ошибок. Второй метод контроля (цифровой контроль) по модулю преду- сматривает суммирование значений разрядов числа по некоторому 242 модулю в соответствии с выражением 1 0 mod k m i i b m α − = = ∑ , где i b - значение i -го разряда числа; k - число разрядов. Например, для числа x = 1001 контрольный разряд при m = 2 имеет значение [ ] 2 1 0 0 1 mod 2 0 α = + + + = и поэтому избыточный код будет следующим: 2 1001 0 х = контрольный разряд. Очевидно, что при таком кодировании для m = 2 все неисправ- ности, приводящие к искажению одного разряда (трех, пяти и т.д.), обнаруживаются. Если же искажаются два разряда (четыре, шесть и т.д.), то ошибка не будет обнаружена. Однако вероятность появления ошибок одновременно в двух разрядах существенно меньше появле- ния одиночных ошибок. Схемные методы контроля по модулю 2 называются также кон- тролем по четности. Если контрольным разрядам присваиваются ин- версные значения ( 2 α ), то контроль называется проверкой по нечет- ности. Контроль с проверкой по нечетности (четности) имеет неболь- шую избыточность и не требует больших затрат оборудования для своей реализации. Этот метод широко используется в цифровых уст- ройствах для контроля передачи информации как внутри устройства, так и вне его, а также для контроля информации, считанной из запо- минающего устройства. 6.3.3 Коды, исправляющие ошибки В исправляющих кодах двоичное число, составленное из кон- трольных разрядов (синдром кода), должно определять порядковый номер искаженного разряда кодового слова. Далее значение искажен- ного разряда инвертируется, чем достигается его коррекция. 243 Примером таких кодов является код Хэмминга. В этом коде кон- трольные суммы составляются так, чтобы в сумму j s входили симво- лы кодового слова, имеющие единицу в j - м разряде в двоичной за- писи их порядкового номера. Нетрудно видеть, что при этом симво- лы, порядковый номер которых в двоичной записи выражается еди- ницей j - го разряда, т.е. равен 1 2 , 1, 2, 3,..., j j − = войдут только в одну контрольную сумму j s . Именно на этих позициях (1-й, 2-й, 4-й, 8-й, ..., 2 i ) в коде Хэмминга и располагаются проверочные символы 2 1 2 4 8 , , , ,... i β β β β β . Соответствующим их выбором все контрольные суммы обращаются в нуль. При отсутствии искажений все контроль- ные суммы останутся равными нулю. Одиночная ошибка, например искажение l - го разряда кодового слова, приведет к обращению в единицу контрольных сумм, номера которых соответствуют номерам разрядов двоичной записи числа l , содержащих единицы. Поэтому, записывая значения контрольных сумм в порядке убывания их номе- ров, т.е. записывая синдром 4 3 2 1 ... , , , s s s s , получаем в двоичной записи номер l искаженного разряда. Для наглядности двоичная запись номеров разрядов кодового слова сведена в таблицу 6.1 (таблица приведена для информационных сообщений, представленных в виде пятнадцатиразрядных кодов). Для пятнадцатиразрядного кода в соответствии с таблицей 6.1 контрольные суммы имеют вид: 1 1 3 5 7 9 11 13 15 2 2 3 6 7 10 11 14 15 3 4 5 6 7 12 13 14 15 4 8 9 10 11 12 13 14 15 ; ; ; s b b b b b b b s b b b b b b b s b b b b b b b s b b b b b b b β β β β = ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ (6.5) где i b - значение информационных символов кода; 1 2 4 8 , , , β β β β - значения проверочных символов; ⊕ - знак суммирования по модулю два. 244 Таблица 6.1 Значения разрядов двоичной записи порядкового номера разрядов кода Порядковый номер разряда 4 3 2 1 (младший) 1 (младший) 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1 Значения проверочных символов i β , отображающие в нуль кон- трольные суммы равны 1 3 5 7 9 11 13 15 2 3 6 7 10 11 14 15 4 5 6 7 12 13 14 15 8 9 10 11 12 13 14 15 ; ; ; b b b b b b b b b b b b b b b b b b b b b b b b b b b b β β β β = ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ (6.6) Процедура формирования исправляющего кода Хэмминга вклю- чает, таким образом, следующие операции: 1) расположение информационных символов в порядке возрас- тания разрядов (справа налево) с сохранением незанятыми разрядов с номерами 1 2 j − , т.е. 1-го, 2-го, 4-го, 8-го и т.д.; 2) вычисление проверочных символов, занимающих разряды с номерами 1 2 j − , по формулам (6.6). Процедура определения передаваемого информационного кода при использовании исправляющего кода Хэмминга включает: 1) вычисление контрольных сумм по формулам (6.5); 2) определение порядкового номера искаженного символа, если 245 не все контрольные суммы равны нулю, и исправление его на другой двоичный символ; 3) выделение информационного кода исключением разрядов с номерами 1 2 , 1, 2,... j j − = Например, если информационный код имеет вид 101001, то его символы располагаются в коде Хэмминга в следующей последова- тельности: 10 9 8 7 6 5 4 3 2 1 1 0 8 β 1 0 0 4 β 1 2 β 1 β Определим по формулам (6.3) значения проверочных символов: 1 3 5 7 9 2 3 6 7 10 4 5 6 7 8 1 0 1 0 0; 1 0 1 1 1; 0 0 1 1; 0. b b b b b b b b b b b β β β β = ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕ = = ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕ = = ⊕ ⊕ = ⊕ ⊕ = = С учетом контрольных разрядов получим следующий код: 1001001110. Если, например, при приеме пятый разряд этого кода ошибочно будет принят как единица, то контрольные суммы (синдромы) будут иметь значения: 1 1 3 5 7 9 2 2 3 6 7 10 3 4 5 6 4 8 0 1 1 1 0 1; 1 1 0 1 1 0; 1 1 0 1 1; 0. s b b b b s b b b b s b b s β β β β = ⊕ ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕ ⊕ = = ⊕ ⊕ ⊕ ⊕ = ⊕ ⊕ ⊕ ⊕ = = ⊕ ⊕ = ⊕ ⊕ ⊕ = = = Значение синдрома, определяющего номер искаженного разряда в двоичной записи, равно 4 3 2 1 0101 s s s s = , что соответствует двоично- му представлению цифры 5 десятичной системе счисления. Для ис- правления ошибки требуется изменить символ в 5-м разряде. 246 6.3.4 Каскадные коды Возможности кода по обнаружению и исправлению ошибок оп- ределяются величиной избыточности кода. Причем практически без- ошибочная передача информации достигается лишь при весьма зна- чительных длинах кодовых слов. Поиск эффективных схем кодирова- ния и декодирования, сложность реализации которых с ростом длины кода увеличивалась бы как можно медленнее, привел к появлению каскадных кодов. Обобщенный каскадный код определяется так. Двоичное слово α длины 1 2 n n n = ⋅ является кодовым словом обобщенного каскадно- го кода порядка m тогда и только тогда, когда все связанные со сло- вом α , векторы , 1, 1 i i m γ = + , представляют собой кодовое слово соответствующих ( ) i x − кодов второй ступени. Обобщенному каскадному коду можно дать достаточно нагляд- ную и удобную при многих рассуждениях геометрическую трактовку. Последовательность α двоичных символов, образующих кодо- вое слово обобщенного каскадного кода, разместим в прямоугольную таблицу размером 1 2 n n ⋅ так, что векторы j α являются ее столбцами. Тогда векторы 1 2 2 , ,..., i i n α α α образуют i -й горизонтальный блок i B этой таблицы, общее число которых равно 1 m + , где m - порядок кода. Каждый горизонтальный блок i B , состоящий из i α строк, в свою очередь, разобьем на два блока - i К и i L , содержащих соответственно i b и 2 i n b − столбцов. В блоках i К расположены информационные символы каскадно- го кода, а в блоках i L - его проверочные символы (рисунок 6.1). Если 1 m b + = 0, то блок 1 m B + совпадает с 1 m L + и содержит одни лишь прове- рочные символы (рисунок 6.2). В этом случае столбцы j α являются кодовыми словами некото- рого двоичного линейного кода длины 1 n . Отметим, что величины 0 i a > и 0 i b ≥ , определяющие внутрен- нюю структуру обобщенного каскадного кода, могут выбираться произвольно, при этом общее число k информационных символов и r проверочных символов равны |