WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 10 | 11 || 13 |

Сложение операндов и сложение вычетов операндов для случая отсутствия ошибки при сложении:

Операнд Вычет Комментарий 0 0 1 0 1 0 1 1 0 0 1 операнд N1; вычет RN0 0 1 1 0 0 0 1 0 0 0 операнд N2; вычет RN0 1 0 1 1 1 0 0 0 0 1 сложение операндов и вычетов (0 1) (0 1 1) (1 0 0) 0 0 1 вычисление вычетов RN3 и RN1+RN1 Так как вычет суммы операндов равен сумме вычетов операндов, считается, что результат сложения верен Сложение операндов и сложение вычетов операндов для случая возникновения ошибки при сложении:

Операнд Вычет Комментарий 0 0 1 0 1 0 1 1 0 0 1 операнд N1; вычет RN0 0 1 1 0 0 0 1 0 0 0 операнд N2; вычет RN0 1 0 0 1 1 0 0 0 0 1 сложение операндов и ошибка вычетов (0 1) (0 0 1) (1 0 0) 0 0 1 вычисление вычетов RNи RN1+RN6 Так как вычет суммы операндов не равен сумме вычетов операндов, считается, что результат сложения не верен Пример 2. Контроль сложения тех же операндов осуществим по модулю 3. Вычисление вычетов операндов дает следующий результат:

RN1=1;

RN2=1.

Сложение операндов и сложение вычетов операндов для случая отсутствия ошибки при сложении:

Операнд Вычет Комментарий 0 0 1 0 1 0 1 1 0 1 операнд N1; вычет RN0 0 1 1 0 0 0 1 0 1 операнд N2; вычет RN0 1 0 1 1 1 0 0 1 0 сложение операндов и вычетов (0 1) (0 1) (1 1) (0 0) 1 0 вычисление вычетов RN3 и RN1+RN2 Так как вычет суммы операндов равен сумме вычетов операндов, считается, что результат сложения верен Сложение операндов и сложение вычетов операндов для случая возникновения ошибки при сложении:

Операнд Вычет Комментарий 0 0 1 0 1 0 1 1 0 1 операнд N1; вычет RN0 0 1 1 0 0 0 1 0 1 операнд N2; вычет RN0 1 0 1 1 0 ошибка 0 0 1 0 сложение операндов и вычетов (0 1) (0 1) (1 0) (0 0) 1 0 вычисление вычетов RN3 и RN1+RN1 Так как вычет суммы операндов не равен сумме вычетов операндов, считается, что результат сложения не верен 5.2. Контроль арифметических операций над беззнаковыми числами Контроль арифметических операций над беззнаковыми числами выполняется в соответствии со всеми вышеизложенными положениями, но только при получении вычета суммы (разности) учитывается значение флага CF.

Рассмотрим выполнение контроля операции сложения на примере сложения операндов в восьмиразрядном процессоре:

N3=N1+N2;

N1=246(8)=10100110(2);

N2=177(8)=01111111(2).

Пример 1. Контроль осуществляется по модулю 7. Вычисление вычетов операндов дает следующий результат:

RN1=5;

RN2=1.

Сложение операндов и сложение вычетов операндов для случая отсутствия ошибки при сложении:

CF Операнд Вычет Комментарий * 1 0 1 0 0 1 1 0 1 0 1 операнд N1; вычет RN* 0 1 1 1 1 1 1 1 0 0 1 операнд N2; вычет RN1 0 0 1 0 0 1 0 1 1 1 0 сложение операндов и вычетов (1 0 1) (0 1 1) (1 0 1) 1 1 0 вычисление вычета RN3 с учетом CF и RN1+RN6 Так как вычет суммы операндов равен сумме вычетов операндов, считается, что результат сложения верен Сложение операндов и сложение вычетов операндов для случая возникновения ошибки при сложении:

CF Операнд Вычет Комментарий * 1 0 1 0 0 1 1 0 1 0 1 операнд N1; вычет RN* 0 1 1 1 1 1 1 1 0 0 1 операнд N2; вычет RN1 0 0 1 0 0 0 ошибка 0 1 1 1 0 сложение операндов и вычетов (1 0 1) (0 1 1) (0 0 1) 1 1 0 вычисление вычета RN3 с учетом CF и RN1+RN2 Так как вычет суммы операндов не равен сумме вычетов операндов, считается, что результат сложения не верен Пример 2. Контроль сложения тех же самых операндов осуществляется по модулю 3. Вычисление вычетов операндов дает следующий результат:

RN1=1;

RN2=1.

Сложение операндов и сложение вычетов операндов для случая отсутствия ошибки при сложении:

CF Операнд Вычет Комментарий * 1 0 1 0 0 1 1 0 0 1 операнд N1; вычет RN* 0 1 1 1 1 1 1 1 0 1 операнд N2; вычет RN 0 1 0 1 1 1 0 0 1 0 сложение (1) (0 0) (1 0) (0 1) (0 1) 1 0 вычисление вычета 2 Так как вычет суммы операндов равен сумме вычетов операндов, считается, что результат сложения верен Сложение операндов и сложение вычетов операндов для случая возникновения ошибки при сложении:

CF Операнд Вычет Комментарий * 1 0 1 0 0 1 1 0 0 1 операнд N1; вычет RN* 0 1 1 1 1 1 1 1 0 1 операнд N2; вычет RN 0 1 0 1 1 ошиб- 1 0 0 1 сложение операндов и вычетов ка (1) (0 0) (1 0) (1 1) (0 1) 1 0 вычисление вычета RN3 с учетом CF и RN1+RN1 Так как вычет суммы операндов не равен сумме вычетов операндов, считается, что результат сложения не верен Рассмотрим выполнение контроля операции вычитания на примере вычитания операндов в восьмиразрядном процессоре в дополнительном коде:

N3=N1–N2=N1+(–N2);

N1=44(8)=00100100(2);

N2=42(8)=00100010(2);

–N2= –42(8)= –00100010 (2); [–N2]2=11011110.

Пример. Контроль осуществляется по модулю 7. Вычисление вычетов операндов дает следующий результат:

RN1=1;

–RN2=5.

Вычитание операндов и вычитание вычетов операндов для случая отсутствия ошибки при сложении (вычитание заменено на сложение с –N2):

CF Операнд Вычет Комментарий * 0 0 1 0 0 1 0 0 0 0 1 операнд N1; вычет RN* 1 1 0 1 1 1 1 0 1 0 1 операнд N2; вычет RN1 0 0 0 0 0 0 1 0 0 0 1 сложение (1 0 0) (0 0 0) (0 1 0) 1 1 0 вычисление вычета 6 Так как вычет разности операндов равен разности вычетов операндов, считается, что результат сложения верен Вычитание операндов и вычитание вычетов операндов для случая возникновения ошибки при сложении:

CF Операнд Вычет Комментарий * 0 0 1 0 0 1 0 0 0 0 1 операнд N1; вычет RN* 1 1 0 1 1 1 1 0 1 0 1 операнд N2; вычет RN1 0 1 0 0 0 0 1 0 1 1 0 вычитание операндов и вычетов ошибка (1 0 1) (0 0 0) (0 1 0) 1 1 0 вычисление вычета RN3 с учетом CF и RN1+RN0 Так как вычет суммы операндов не равен сумме вычетов операндов, считается, что результат сложения не верен Рассмотрим выполнение контроля операции умножения на примере умножения операндов в восьмиразрядном процессоре в прямом коде:

Пример. N3=N1*N2;

N1=121(8)=01010001(2);

N2=41(8)=00100001(2).

Контроль осуществляется по модулю 7. Вычисление вычетов операндов дает следующий результат:

RN1=4;

RN2=5.

Результат умножения N3=N1*N2 равен 0000101001110001(2) (выполнение алгоритма здесь не приводится). Вычет произведения (0)(000)(101)(001)(110)(001) равен 6.

Произведение вычетов равно RN1*RN2=4*5=20(10), mod7(20)=6.

Так как вычет произведения равен вычету от произведения вычетов, результат операции считается верен.

Если при умножении произошла ошибка и получен неверный результат, например, N3=N1*N2=0000101001110000, то вычет произведения будет равен 5 и не равен вычету от произведения вычетов, т.е.

результат операции не верен.

Рассмотрим выполнение контроля операции деления на примере деления операндов в восьмиразрядном процессоре в прямом коде.

Пример. N3=N1/N2;

N1=241(8)=10100001(2);

N2=24(8)=00010100(2).

Контроль осуществляется по модулю 3. Вычисление вычетов операндов дает следующий результат:

RN1=2;

RN2=2.

Результат деления, т.е. частное N3=N1/N2, равен 00001000(2), остаток N4 равен 00000001(2) (выполнение алгоритма здесь не приводится). Вычет частного RN3 от N3=(00)(00)(10)(00) равен 2. Вычет остатка RN4 от N4=(00)(00)(00)(01) равен 1. Тогда вычет от RN2*RN3+RN4= =2*2+1=5(10) по mod3(5)=2.

Так как вычет делимого равен вычету от произведения вычетов делителя и частного с добавлением вычета от остатка, результат операции считается верным.

Если при делении произошла ошибка и получен неверный результат, например, N3=N1/N2=000001001(2) и N4=00000001(2), то вычет делимого не равен вычету от произведения вычетов делителя и частного с добавлением вычета от остатка, результат операции считается неверным:

RN2*RN3+ RN4=2*0+1=1(10) по mod3(1)=1.

5.3. Выполнение контроля арифметических операций над числами со знаком Рассмотрим такой контроль только для процессора, работающего в дополнительном коде. В этом случае при получении вычета знаковый разряд учитывается как числовой. Все остальные положения по контролю совпадают с контролем арифметических операций без знака.

Рассмотрим выполнение контроля операции сложения на примере сложения операндов в восьмиразрядном процессоре в дополнительном коде:

N3=N1+N2;

N1= –44(8)= –00100100(2);

N2= –42(8)= –00100010(2);

[N1]2=11011100;

[N2]2=11011110.

Пример. Контроль осуществляется по модулю 7. Вычисление вычетов дополнительного кода операндов дает следующий результат:

RN1=3;

RN2=5.

Сложение операндов и сложение вычетов операндов для случая отсутствия ошибки при сложении:

CF Операнд Вычет Комментарий * 1 1 0 1 1 1 0 0 0 1 1 операнд N1; вычет RN* 1 1 0 1 1 1 1 0 1 0 1 операнд N2; вычет RN1 1 0 1 1 1 0 1 0 0 0 1 сложение операндов и вычетов (1 1 0) (1 1 1) (0 1 0) 0 0 1 вычисление вычета RN3 с учетом CF и RN1+RN1 Так как вычет суммы операндов равен сумме вычетов операндов, считается, что результат сложения верен Сложение операндов и сложение вычетов операндов для случая возникновения ошибки при сложении:

CF Операнд Вычет Комментарий * 1 1 0 1 1 1 0 0 0 1 1 операнд N1; вычет RN* 1 1 0 1 1 1 1 0 1 0 1 операнд N2; вычет RN1 1 1 1 1 1 0 1 0 0 0 1 сложение операндов и вычетов ошибка (1 1 1) (1 1 1) (0 1 0) 0 0 1 вычисление вычета RN3 с учетом CF и RN1+RN2 Так как вычет суммы операндов не равен сумме вычетов операндов, считается, что результат сложения не верен 6. Контроль передачи информации в цифровых каналах связи В цифровых каналах связи (рис. 6.1) при передаче информации по разным причинам (неисправность оборудования, помехи) могут возникать ошибки. Поэтому на приемной стороне используются различные способы обнаружения ошибок, а также способы, позволяющие выполнить как обнаружение, так исправление ошибки.

Источник Приемник информации информации Рис. 6.1. Канал связи Если контроль передачи информации выполняется только с обнаружением ошибки, то в случае ошибки приемник запрашивает повторную передачу искаженной информации. Если же контроль выполняется с обнаружением и исправлением ошибки, то приемник сам выполняет коррекцию искаженной информации без обращения к передатчику.

Из теории кодирования информации известно, что вероятность двойной или тройной ошибки (в двух или трех битах одновременно) на один или два порядка меньше, чем вероятность возникновения одиночной ошибки. Поэтому при контроле передачи информации основное внимание уделяется обнаружению, а также обнаружению и исправлению одиночной ошибки. Различают коды, которые позволяют только обнаруживать ошибку, и коды, которые позволяют как обнаруживать, так и исправлять ее.

6.1. Коды для обнаружения ошибок Наиболее часто для обнаружения ошибок используется контроль на четность/нечетность передаваемой информации. При таком контроле блок информации, передаваемый от источника к приемнику, должен содержать соответственно четное/нечетное число единиц.

Источник формирует передаваемый блок информации так, чтобы это выполнялось. Приемник проверяет выполнение этого условия. Если четность/нечетность нарушена, то считается, что произошла ошибка при передаче информации. Приемник сообщает об этом источнику, и источник заново посылает этот блок информации. Передаваемый блок информации состоит из информационных битов и одного контрольного:

Передаваемый блок информации Информационные биты Контрольный бит x1, x2,….xn k При контроле на четность в бит k записывается сумма по модулю 2 информационных разрядов. При контроле на нечетность записывается инверсное значение этой суммы.

Рассмотрим пример такого контроля. Пусть от источника к приемнику надо переслать 8 бит информации с контролем на четность.

Тогда пересылаемый блок информации должен содержать 9 бит.

Пример. Переслать код 01110101.

Побитное сложение по модулю для этого кода дает значение, равное 1. Тогда значение контрольного бита должно равняться 1, чтобы передаваемый код содержал четное число единиц.

Передатчик Приемник Сумма Комментарий Информационные Контрольный Принятые биты по бит биты mod0 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 0 нет ошибки 0 1 1 1 1 1 0 1 1 1 есть ошибка 6.2. Код Хэмминга для обнаружения и исправления ошибки Исправлять ошибку при приеме информации труднее, чем ее обнаруживать. Исправление ошибки предполагает два совмещенных процесса: обнаружение факта, что есть ошибка, и определение ее места. После решения этих двух задач, исправление тривиально – надо инвертировать значение ошибочного бита. В наземных каналах связи, где вероятность ошибки невелика, обычно используется только метод обнаружения ошибки и повторной пересылки блока информации, содержавшего ошибку. Для спутниковых каналов с типичны ми для них большими задержками коррекция ошибки становится необходимой. Здесь используется код Хэмминга.

Код Хэмминга представляет собой блочный код, который позволяет выявить и исправить ошибочно переданный бит в пределах переданного блока. Блочными называются коды, в которых информационный поток символов разбивается на отрезки, и каждый из них преобразуется в определенную последовательность (блок) кодовых символов. В блочных кодах кодирование при передаче (формирование проверочных элементов) и декодирование при приеме (обнаружение и исправление ошибок) выполняются в пределах каждой кодовой комбинации (блока) в отдельности по соответствующим алгоритмам.

Обычно код Хэмминга характеризуется двумя целыми числами, например, код (11,7), используемый при передаче семибитных ASCII-кодов. Такая запись говорит, что при передаче семибитного кода используется дополнительно четыре контрольных бита (7+4=11). При этом предполагается, что может иметь место ошибка в одном бите и что ошибка в двух или более битах существенно менее вероятна. С учетом этого исправление ошибки осуществляется с определенной вероятностью.

При рассмотрении кода Хэмминга требуется знать, что такое кодовое расстояние. Кодовое расстояние между двумя двоичными кодами одинаковой длины определяется количеством битов, в которых эти коды отличаются.

Пример 1. Кодовое расстояние между «кодом 1» и «кодом 2» равно 1.

код 1 0 1 код 2 0 1 Пример 2. Кодовое расстояние между «кодом 1» и «кодом 2» равно 2.

код 1 0 0 код 2 1 1 Можно обнаружить ошибку только, если между используемыми кодовыми комбинациями есть необходимое для этого кодовое расстояние, т.е. между соседними используемыми кодовыми комбина циями есть другие комбинации. Эти кодовые комбинации не используются для передачи информации, и их получение на приеме свидетельствует об ошибке передачи информации в канале связи. Для заданного кода минимальное кодовое расстояние – это минимальное из всех расстояний всех пар кодовых слов.

В обычном равномерном непомехоустойчивом коде число разрядов n в кодовых комбинациях определяется числом сообщений и основанием кода. Коды, у которых все кодовые комбинации разрешены к передаче, называются простыми или равнодоступными и являются полностью безызбыточными. Безызбыточные первичные коды обладают большой «чувствительностью» к помехам. Внесение избыточности при использовании помехоустойчивых кодов обязательно связано с увеличением числа разрядов (длины) кодовой комбинации.

В этом случае все множество N=2n комбинаций можно разбить на два подмножества: подмножество разрешенных комбинаций, т.е. обладающих определенными признаками, и подмножество запрещенных комбинаций, этими признаками не обладающих. Помехоустойчивый код отличается от обычного тем, что в канал передаются не все кодовые комбинации N, которые можно сформировать из имеющегося числа разрядов n, а только их часть NК, которая составляет подмножество разрешенных комбинаций Если при приеме выясняется, что кодовая комбинация принадлежит к запрещенным, то это свидетельствует о наличии ошибки, т.е.

таким образом решается задача обнаружения ошибок. При этом принятая комбинация не декодируется (не принимается решение о приеме сообщения). Помехоустойчивые коды называют корректирующими кодами. Корректирующие свойства избыточных кодов зависят от правила их построения, определяющего структуру кода, и параметров кода.

Первые работы по корректирующим кодам принадлежат Хэммингу, который ввел понятие минимального кодового расстояния и предложил код, позволяющий однозначно указать ту позицию в кодовой комбинации, где произошла ошибка. К «M» (message) информационным битам в коде Хэмминга добавляется «C» (control) проверочных битов для определения местоположения ошибочного бита.

Таким образом, код Хэмминга состоит из информационных и контрольных битов. Информационные биты будем обозначать через М, контрольные биты – через С:

М={M1,M2,…Mn};

C={C1, C2,…Ck};

N=M+C – общее количество передаваемых битов в канал связи (передаваемый блок).

Pages:     | 1 |   ...   | 10 | 11 || 13 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.