Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Дипломная работа: Корректирующие коды

Название: Корректирующие коды
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Добавлен 04:29:20 28 июля 2009 Похожие работы
Просмотров: 1760 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Курс: Теория информации и кодирования

Тема: КОРРЕКТИРУЮЩИЕ КОДЫ

Содержание

1. КОРРЕКТИРУЮЩИЕ КОДЫ. ОСНОВНЫЕ ПОНЯТИЯ

2. ЛИНЕЙНЫЕ ГРУППОВЫЕ КОДЫ

3. КОД ХЭММИНГА

Список Литературы


1. КОРРЕКТИРУЮЩИЕ КОДЫ. ОСНОВНЫЕ ПОНЯТИЯ

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

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

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

В ЭВМ эти коды используются для повышения надежности оперативной памяти (ОП) и магнитных дисков. Число ошибок в ЭВМ зависит от типа неисправностей элементов схем (например, неисправность одного элемента интегральной схемы (ИС) вызывает одиночную ошибку, а всей ИС ОП - кратную). Для обнаружения кратных ошибок используется код КО-ОД-ООГ (коррекция одиночной, обнаружение двойной и обнаружение кратной ошибки в одноименной группе битов).

Среди корректирующих кодов широко используются циклические коды, в ЭВМ эти коды применяются при последовательной передаче данных между ЭВМ и внешними устройствами, а также при передаче данных по каналам связи. Для исправления двух и более ошибок (d0 ³ 5 ) используются циклические коды БЧХ (Боуза - Чоудхури - Хоквингема), а также Рида-Соломона, которые широко используются в устройствах цифровой записи звука на магнитную ленту или оптические компакт-диски и позволяющие осуществлять коррекцию групповых ошибок. Способность кода обнаруживать и исправлять ошибки достигается за счет введений избыточности в кодовые комбинации, т. е. кодовым комбинациям из к двоичных информационных символов, поступающих на вход кодирующего устройства, соответствует на выходе последовательность из n двоичных символов (такой код называется (n, k ) - кодом).

Если N0 = 2n -общее число кодовых комбинаций, а N = 2k - число разрешенных, то число запрещенных кодовых комбинаций равно

N0 -N = 2n -2k .

При этом число ошибок, которое приводит к запрещенной кодовой комбинации равно:

, (1)

где S - кратность ошибки, т. е. количество искаженных символов в кодовой комбинации S = 0, 1, 2, ...

Cn i - сочетания из n элементов по i , вычисляемое по формуле:

, (2)

дляS = 0 ;

S = 1 ;

S = 2 ;

S = 3 ; ит. д.

Для исправления S ошибок количество комбинаций кодового слова, составленного из m проверочных разрядов N = 2m , должно быть больше возможного числа ошибок (2), при этом количество обнаруживаемых ошибок в два раза больше, чем исправляемых

(3)

2m ³ откуда .

Для одиночной ошибки, как наиболее вероятной .

В зависимости от исходных данных кода (n или k ) можно использовать

формулы

. (4)

При этом, m = [log2 (1+n)] или m = [log2 {(k+1)+ [log2 (k+1)]}], где ква-дратные скобки обозначают округление до большего целого.

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

Для исправления двукратной ошибки

или . (5)

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

Например, для кода (31, 26) скорость передачи информации равна

,

т. е. скорость передачи уменьшается на 16%.

Таблица 1

n 7 10 15 31 63 127 255
k 4 6 11 26 57 120 247
m 3 4 4 5 6 7 8
0,57 0,6 0,75 0,84 0,9 0,95 0,97

Как видно из таблицы 1, чем больше n, тем эффективнее используется канал.

Пример 1. Определить количество проверочных разрядов для систематического кода исправляющего одиночную ошибку и состоящего из 20 информационных разрядов.

Решение: Общая длина кодовой комбинации равна n = k+m, где k - количество информационных разрядов, а m - проверочных разрядов.

Для обнаружения двойной и исправления одиночной ошибки зависимости для разрядов имеют вид , при этом

m = [log2 {(k+1)+ [log2 (k+1)]}]=[log2 {(20+1)+ [log2 (20+1)]}]=5,

т. е. получим (25, 20)-код.

2. ЛИНЕЙНЫЕ ГРУППОВЫЕ КОДЫ

Линейным называется код, в котором проверочные символы представляют собой линейные комбинации информационных. Групповым называется код, который образует алгебраическую группу по отношению операции сложения по модулю два.

Свойство линейного кода : сумма (разность) кодовых векторов линей-ного кода дает вектор, принадлежащий этому коду. Свойство группового кода: минимальное кодовое расстояние между кодовыми векторами равно минимальному весу ненулевых векторов. Вес кодового вектора равен числу единиц в кодовой комбинации.

Групповые коды удобно задавать при помощи матриц, размерность которых определяется параметрами k и n . Число строк равно k, а число столбцов равно n = k+m.

. (6)


Коды, порождаемые этими матрицами, называются (n, k )-кодами, а соответствующие им матрицы порождающими (образующими, производящими). Порождающая матрица G состоит из информационной Ikk и проверочной Rkm матриц. Она является сжатым описанием линейного кода и может быть представлена в канонической (типовой) форме

. (7)

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

. (8)

Строки единичной матрицы представляют собой линейно-незави-симые комбинации (базисные вектора), т. е. их по парное суммирование по модулю два не приводит к нулевой строке.

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

Столбцы добавочной матрицыRkm определяют правила формирования проверок. Число единиц в каждой строке добавочной матрицы должно удовлетворять условию r1 ³ d0 -1 , но число единиц определяет число сумматоров по модулю 2 в шифраторе и дешифраторе, и чем их больше, тем сложнее аппаратура.

Производящая матрица кода G(7,4) может иметь вид

и т.д.

Процесс кодирования состоит во взаимно - однозначном соответствии k -разрядных информационных слов - I и n- разрядных кодовых слов - с

c=IG. (9)

Например: информационному слову I =[1 0 1 0] соответствует следующее кодовое слово

. (10)

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

Процесс декодирования состоит в определении соответствия принятого кодового слова, переданному информационному. Это осуществляется с помощью проверочной матрицы H(n, k) .

, (11)


где Rmk T -транспонированная проверочная матрица (поменять строки на столбцы); Imm - единичная матрица.

Для (7, 4)- кода проверочная матрица имеет вид

. (12)

Между G(n ,k) и H(n, k) существует однозначная связь, т. к. они определяются в соответствии с правилами проверки, при этом для любого кодового слова должно выполняться равенство cHT = 0 .

Строки проверочной матрицы определяют правила формирования проверок. Для (7, 4)-кода

p1 Å +a1 Å +a2 Å a4 = S1 ;

p2 Å +a1 Å +a2 Å a3 = S2 ; (13)

p 3 Å + a 1 Å + a 3 Å a 4 = S 3 .

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

Пример 1. Построить групповой код способный передавать 16 символов первичного алфавита с исправлением одиночной ошибки. Показать процесс кодирования, декодирования и исправления ошибки для передаваемого информационного слова 1001.

Решение:

1. Построим производящую матрицу G(n, k) .

Если объем кода N = 2k = 16, то количество информационных разрядов к = 4. Минимальное кодовое расстояние для исправления одиночной ошибки d0 =2s+1=3. По заданной длине информационного слова, используя соотношения:

n = k+m, 2n ³ (n+1)2k и 2m ³ n+1

вычислим основные параметры кода n и m .

m=[log2 {(k+1)+ [log2 (k+1)]}]=[log2 {(4+1)+ [log2 (4+1)]}]=3.

Откуда n = 7 , т. е. необходимо построить (7, 4)-код.

В качестве информационной матрицы Ik (7, 4) - выбираем единичную матрицу (4´4), а в качестве проверочной матрицы Rkm (7 ,4) - выбираем матрицу (4´3), каждая строка которой содержит число единиц больше или равно двум (r1 £ d0 -1 ).

Таким образом, в качестве производящей можно принять матрицу

.

2. Определим комбинации корректирующего кода.

Для заданного числа информационных разрядов k = 4, число кодовых комбинаций равно N = 2k = 24 = 16 .

1) 0000 5) 0010 9) 0001 13) 0011

2) 1000 6) 1010 10) 1001 14) 1011

3) 0100 7) 0110 11) 0101 15) 0111

4) 1100 8) 1110 12) 1101 16) 1111

Старшинство разрядов принимаем слева на право, в соответствии с их поступлением на вход декодера.

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

Например, для информационного слова I = [1001] кодовое слово имеет вид

.

Передаваемые в канал кодовые комбинации имеют вид:

1) 0000 000 5) 0010 110 9) 0001 101 13) 0011 011

2) 1000 111 6) 1010 001 10) 1001 010 14) 1011 100

3) 0100 011 7) 0110 101 11) 0101 110 15) 0111 000

4) 1100 100 8) 1110 010 12) 1101 101 16) 1111 111

Процесс декодирования состоит в определении соответствия принятого кодового слова, переданному информационному и осуществляется с помощью проверочной матрицы H(7, 4) .


Для построенного (7, 4)-кода проверочная матрица имеет вид

.

Строки проверочной матрицы определяют правила формирования проверок, позволяющие определить синдром ошибки.

Пусть в процессе передачи произошла ошибка во 2-м информационном разряде 1 1 0 1 1 0 0 1

В соответствии с проверочной матрицей составляем проверочные векторы

p1 Å a1 Å a2 Å a4 =S1 = 0 Å 1 Å 1 Å 0 = 0;

p2 Å a1 Å a2 Å a3 =S2 = 0 Å 1 Å 1 Å 1 = 1 ;

p3 Å a1 Å a3 Å a4 =S3 = 1 Å 1 Å 0 Å 1 = 1.

Синдром 011 показывает, что ошибка произошла во 2-м информационном разряде, который необходимо проинвертировать.

Пример 2. Построить образующую матрицу группового кода, для передачи 100 различных сообщений и способную исправлять возмож-но большее число ошибок.

Решение: Объем кода равен N = 2k . При 100 сообщениях: 100 £ N £ 2k , откуда k = 7 . По заданной длине информационного слова, используя соотношения:

n = k+m, 2n ³ (n+1)2k и 2m ³ n+1

вычислим основные параметры кода n и m .

m=[log2 {(k+1)+ [log2 (k+1)]}]=[log2 {(7+1)+ [log2 (7+1)]}]=4.

Откуда n = 11, т. е. получили (11, 7)-код.

В качестве информационной матрицы выбираем единичную матрицу I (7x7).Проверочная матрица содержит 4 столбца и 7 строк, которые содержат r1 £ d0 -1 единиц в четырехразрядном коде (2, 3, 4-единицы).

.

3. КОД ХЭММИНГА

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

Код Хэмминга, как и любой (n, k )- код, содержит к информационных и m = n-k избыточных (проверочных) бит.

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

Существуют различные методы реализации кода Хэмминга и кодов которые являются модификацией кода Хэмминга. Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

1. По заданному количеству информационных символов - k , либо информационных комбинаций N = 2k , используя соотношения:

n = k+m, 2n ³ (n+1)2k и 2m ³ n+1 (14)

m = [log2 {(k+1)+ [log2 (k+1)]}]

вычисляют основные параметры кода n и m .

2. Определяем рабочие и контрольные позиции кодовой комбинации. Номера контрольных позиций определяются по закону 2i , где i =1, 2, 3,... т.е. они равны 1, 2, 4, 8, 16,… а остальные позиции являются рабочими.

3. Определяем значения контрольных разрядов (0 или 1 ) при помощи многократных проверок кодовой комбинации на четность. Количество проверок равно m = n-k . В каждую проверку включается один контро-льный и определенные проверочные биты. Если результат проверки дает четное число, то контрольному биту присваивается значение -0, в противном случае - 1. Номера информационных бит, включаемых в каждую проверку, определяются по двоичному коду натуральных n –чисел разрядностью – m (табл. 1, для m = 4) или при помощи проверочной матрицы H ( m ´ n ), столбцы которой представляют запись в двоичной системе всех целых чисел от 1 до 2 k 1 перечисленных в возрастающем порядке. Для m = 3 проверочная матрица имеет вид

. (15 )


Количество разрядов m - определяет количество проверок.

В первую проверку включают коэффициенты, содержащие 1 в младшем (первом) разряде, т. е. b1 , b3 , b5 и т. д.

Во вторую проверку включают коэффициенты, содержащие 1 во втором разряде, т. е. b2 , b3 , b6 и т. д.

В третью проверку - коэффициенты которые содержат 1 в третьем разряде и т. д.

Таблица 1

Десятичные числа

(номера разрядов

кодовой комбинации)

Двоичные числа и их разряды

3 2 1

1

2

3

4

5

6

7

0

0

0

1

1

1

1

0

1

1

0

0

1

1

1

0

1

0

1

0

1

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

Для исправления ошибки необходимо проинвертировать бит в ошибочной позиции. Для исправления одиночной ошибки и обнаружения двойной используют дополнительную проверку на четность. Если при исправлении ошибки контроль на четность фиксирует ошибку, то значит в кодовой комбинации две ошибки.

Схема кодера и декодера для кода Хэмминга приведена на рис. 1.

Пример 1. Построить код Хемминга для передачи сообщений в виде последовательности десятичных цифр, представленных в виде 4 –х разрярных двоичных слов. Показать процесс кодирования, декодирования и исправления одиночной ошибки на примере информационного слова 0101.

Решение:

1. По заданной длине информационного слова (k = 4 ), определим количество контрольных разрядов m , используя соотношение:

m = [log2 {(k+1)+ [log2 (k+1)]}]=[log2 {(4+1)+ [log2 (4+1)]}]=3,

при этом n = k+m = 7 , т. е. получили (7, 4) -код.

2. Определяем номера рабочих и контрольных позиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2i .

Для рассматриваемой задачи (при n = 7 ) номера контрольных позиций равны 1, 2, 4. При этом кодовая комбинация имеет вид:

b1 b2 b3 b4 b5 b6 b7

к1 к2 0 к3 1 0 1

3. Определяем значения контрольных разрядов (0 или 1), используя проверочную матрицу (5).

Первая проверка:

k1 Åb3 Åb5 Åb7 = k1 Å0Å1Å1 будет четной при k1 = 0.

Вторая проверка:

k2 Åb3 Åb6 Åb7 = k2 Å0Å0Å1 будет четной при k2 = 1.

Третья проверка:

k3 Åb5 Åb6 Åb7 = k3 Å1Å0Å1 будет четной при k3 = 0.

1 2 3 4 5 6 7

Передаваемая кодовая комбинация: 0 1 0 0 1 0 1

Допустим принято: 0 1 1 0 1 0 1

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

1) k1 Å b3 Å b5 Å b7 = 0Å1Å1Å1 = 1.

2)k2 Å b3 Å b6 Å b7 = 1Å1Å0Å1 = 1.

3) k3 Å b5 Å b6 Å b7 = 0Å1Å0Å1 =0.

Сравнивая синдром ошибки со столбцами проверочной матрицы, определяем номер ошибочного бита. Синдрому 011 соответствует третий столбец, т. е. ошибка в третьем разряде кодовой комбинации. Символ в 3 -й позиции необходимо изменить на обратный.

Пример 2 . Построить код Хэмминга для передачи кодовой комбинации 1 1 0 1 1 0 1 1. Показать процесс обнаружения и исправления ошибки в соответствующем разряде кодовой комбинации.

Решение: Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

1. По заданной длине информационного слова (k = 8 ) , используя соотношения вычислим основные параметры кода n и m .

m = [log2 {(k+1)+ [log2 (k+1)]}]=[log2 {(9+1)+ [log2 (9+1)]}]=4,

при этом n = k+m = 12 , т. е. получили (12, 8)-код.

2. Определяем номера рабочих и контрольных позиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2i .

Для рассматриваемой задачи (при n = 12 ) номера контрольных позиций равны 1, 4, 8.

При этом кодовая комбинация имеет вид:

b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12

к1 к2 1 к3 1 0 1 к4 1 0 1 1

3. Определяем значения контрольных разрядов (0 или 1) путем много-кратных проверок кодовой комбинации на четность. Количество проверок равно m = n-k . В каждую проверку включается один контрольный и определенные проверочные биты.

Номера информационных бит, включаемых в каждую проверку определяется по двоичному коду натуральных n -чисел разрядностью - m .

0001 b1 Количество разрядов m - определяет количество прове-

0010 b2 верок.

0011 b3 1) к1 Åb3 Åb5 Åb7 Åb9 Å а11 = к1 Å1Å1Å1Å1Å1 =>

0100 b4 четная при к1 =1

0101 b5 2) к2 Åb3 Åb6 Åb7 Åb10 Åb11 = к2 Å1Å0Å1Å0Å1 =>

0110 b6 четная при к2 =1

0111 b7 3)к3 Åb5 Åb6 Åb7 Åb12 = к3 Å1Å0Å1Å1=>

1000 b8 четная при к3 =1

1001 b9 4) к4 Åb9 Åb10 Åb11 Åb12 = к1 Å1Å0Å1Å1 =>

1010 b10 четная при к4 =1

1011 b11

1100 b12

Передаваемая кодовая комбинация: 1 2 3 4 5 6 7 8 9 10 11 12

1 1 1 1 1 0 1 1 1 0 1 1

Допустим, принято: 1 1 1 1 0 0 1 1 1 0 1 1


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

1) к1 Åb3 Åb5 Åb7 Åb9 Åb11 = 1Å1Å0Å1Å1Å1 =1

2) к2 Åb3 Åb6 Åb7 Åb10 Åb11 = 1Å1Å0Å1Å0Å1 =0

3)к3 Åb5 Åb6 Åb7 Åb12 = 1Å0Å0Å1Å1 =1

4) к4 Åb9 Åb10 Åb11 Åb12 = 1Å1Å0Å1Å1 =0

Обнаружена ошибка в разряде кодовой комбинации с номером 0101, т. е. в 5 -м разряде. Для исправления ошибки необходимо проинвертировать 5 -й разряд в кодовой комбинации.


Рис. 1. Схема кодера -а и декодера –б для простого (7, 4) кода Хэмминга

Рассмотрим применение кода Хэмминга. В ЭВМ код Хэмминга чаще всего используется для обнаружения и исправления ошибок в ОП, памяти с обнаружением и исправлением ошибок ECCMemory (ErrorCheckingandCorrecting). Код Хэмминга используется как при параллельной, так и при последовательной записи. В ЭВМ значительная часть интенсивности потока ошибок приходится на ОП. Причинами постоянных неисправностей являются отказы ИС, а случайных изменение содержимого ОП за счет флуктуации питающего напряжения, кратковременных помех и излучений. Неисправность может быть в одном бите, линии выборки разряда, слова либо всей ИС. Сбой может возникнуть при формировании кода (параллельного), адреса или данных, поэтому защищать необходимо и то и др. Обычно дешифратор адреса встроен в м/схему и недоступен для потребителя. Наиболее часто ошибки дают ячейки памяти ЗУ, поэтому главным образом защищают записываемые и считываемые данные.

Наибольшее применение в ЗУ нашли коды Хэмминга с dmin =4, исправляющие одиночные ошибки и обнаруживающие двойные.

Проверочные символы записываются либо в основное, либо специальное ЗУ. Для каждого записываемого информационного слова (а не байта, как при контроле по паритету) по определенным правилам вычисляется функция свертки, результат которой разрядностью в несколько бит также записывается в память. Для 16 -ти разрядного информационного слова используется 6 дополнительных бит (32- 7 бит, 64 –8 бит). При считывании информации схема контроля, используя избыточные биты, позволяет обнаружить ошибки различной кратности или исправить одиночную ошибку. Возможны различные варианты поведения системы:

- автоматическое исправление ошибки без уведомления системы;

- исправление однократной ошибки и уведомление системы только о многократных ошибках;

- не исправление ошибки, а только уведомление системы об ошибках;

Модуль памяти со встроенной схемой исправления ошибок –EOS 72/64 (ECConSimm). Аналог микросхема к 555 вж 1 -это 16 разрядная схема с обнаружением и исправлением ошибок (ОИО) по коду Хэмминга (22, 16), использование которой позволяет исправить однократные ошибки и обнаружить все двух кратные ошибки в ЗУ.

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

В составе ВЖ-1 используются 16 информационных и 6 контрольных разрядов. (DB - информационное слово, CB - контрольное слово).

При записи осуществляется формирование кода, состоящего из 16 информационных и 6 контрольных разрядов, представляющих результат суммирование по модулю 2 восьми информационных разрядов в соответствии с кодом Хэмминга. Сформированные контрольные разряды вместе с информационными поступают на схему и записываются в ЗУ.

(22 ,16)

4 схе(72 ,64)

Рис.2. Схема контроля

При считывании шестнадцатиразрядное слово декодируется, восстанавливаясь вместе с 6 разрядным словом контрольным, поступают на схему сравнения и контроля. Если достигнуто равенство всех контрольных разрядов и двоичных слов, то ошибки нет.

Любая однократная ошибка в 16 разрядном слове данных изменяет 3 байта в 6 разрядном контрольном слове. Обнаруженный ошибочный бит инвертируется.


Список Литературы

1. Гриценко В.М, Недвоичные арифметические корректирующие коды, Пробл. передачи информ., 5:4 (1969), 19–27

2. Злотник Б.М. Помехоустойчивые коды в системах связи.—M.: Радио и связь, 1989.—232 c.

3. Кловский Д.Д. Теория передачи сигналов. –М.: Связь, 1984.

4. Ковалгин Ю.А., Вологдин Э. И. Цифровое кодирование звуковых сигналов. Издательство: Корона-Принт, 2004. – 240с.

5. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М.: Наука, 2006.

6. Микропроцессорные кодеры и декодеры/В.М. Муттер, Г.А. Петров и др.—М.: Радио и связь, 1991.—184 с.

7. Питерсон У., Коды, исправляющие ошибки, пер. с англ., М., 1964.

8. Семенюк В.В. Экономное кодирование дискретной информации. – СПб.: СПбГИТМО (ТУ), 2001

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:24:53 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:38:11 28 ноября 2015

Работы, похожие на Дипломная работа: Корректирующие коды
Теория информации
Лекции по Теории информации Подготовил В.С. Прохоров Содержание Введение 1. Понятие информации. Задачи и постулаты прикладной теории информации 1.1 ...
Так как опознаватели векторов ошибок с единицами в нескольких разрядах устанавливаются как суммы по модулю 2 опознавателей одиночных ошибок в этих разрядах, то для определения ...
Для анализа возможностей линейного (n, k)-кода, а также для упрощения процесса кодирования удобно, чтобы порождающая матрица (Мn,k) состояла из двух матриц: единичной матрицы ...
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 7652 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Техническая диагностика средств вычислительной техники
ГОУ СПО Астраханский колледж вычислительной техники М.В. Васильев преподаватель специальных дисциплин Астраханского колледжа вычислительной техники ...
ECC - код исправления ошибок в поле данных.
Для сигнализации о нормальном окончании проверки ТЭЗ, если все режимы проверочного набора прошли без ошибок, в операционном регистре находится еще один служебный разряд "КТ" (конец ...
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 8253 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Лекции по количественной оценке информации
КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ Общее число неповторяющихся сообщений, которое может быть составлено из алфавита m путем комбинирования по n символов ...
Остальные комбинации кода строятся при помощи образующей матрицы по следующему правилу: корректирующие символы, предназначенные для обнаружения или исправления ошибки в ...
Для исправления одиночной и обнаружения двойной ошибки, кроме проверок по контрольным позициям, следует проводить еще одну проверку на четность для каждого кода.
Раздел: Рефераты по информатике, программированию
Тип: шпаргалка Просмотров: 1767 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Методы позиционирования и сжатия звука
Современные звуковые карты. Аннотация В данной курсовой работе изучаются различные аспекты применения звуковых карт. Рассматриваются способы получения ...
Для еще большего повышения стойкости цифрового сигнала к помехам и искажениям применяется цифровое избыточное кодирование двух типов: проверочные (EDC - Error Detection Code ...
В качестве EDC популярен циклический избыточный код CRC (Cyclic Redundancy Check), суть которого состоит в сложном перемешивании исходной информации в блоке и формированию коротких ...
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Просмотров: 2661 Комментариев: 8 Похожие работы
Оценило: 5 человек Средний балл: 4.2 Оценка: неизвестно     Скачать
Разработка устройства кодирования-декодирования 32-х разрядных слов ...
СОДЕРЖАНИЕ Введение 1 Анализ способов кодирования информации 1.1 Проверка чётности 1.2 Код CRC 1.3 Код Хэмминга 1.4 Код Рида - Соломона 2 Разработка ...
Представим, что хотим разработать код с m битами данных и г контрольных разрядов, который позволил бы исправлять все ошибки в битах.
Эта формула дает нижний предел числа контрольных разрядов, необходимых для исправления одиночных ошибок.
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Просмотров: 895 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Психологический словарь
Борис Гурьевич Мещеряков, Владимир Петрович Зинченко Большой психологический словарь Оглавление Предисловие Персоналии Список авторов Список ...
1) для проверочного (контрольного) чтения ("да - нет", "работает - не работает" и т. п.); 2) для качественного чтения (определение тенденции, направления изменения параметра ...
Первые генерируют максимальный по частоте и числу импульсов разряд при определенном угле поворота одиночной световой (или темповой) полоски или решетки из чередующихся полос в ...
Раздел: Рефераты по психологии
Тип: книга Просмотров: 4612 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Технология цифровой связи
НЕКОММЕРЧЕСКОЕ АКЦИОНЕРНОЕ ОБЩЕСТВО АЛМАТИНСКИИ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ Кафедра автоматической электросвязи ТЕХНОЛОГИИ ЦИФРОВОЙ СВЯЗИ Конспект ...
Второй метод, прямое исправление, требует лишь односторонней линии связи, поскольку в этом случае контрольный бит четности служит как для обнаружения, так и исправления ошибок.
Далее мы увидим, что не все комбинации ошибок можно исправить, так что коды коррекции классифицируются в соответствии с их возможностями исправления ошибок.
Раздел: Рефераты по коммуникации и связи
Тип: учебное пособие Просмотров: 11705 Комментариев: 4 Похожие работы
Оценило: 2 человек Средний балл: 5 Оценка: неизвестно     Скачать
Разработка виртуальных лабораторных работ средствами эмулятора Emu8086
Содержание Введение 1. Виртуальный лабораторный практикум в инженерном образовании 1.1 Особенности лабораторного практикума для естественнонаучных ...
LOOP m1; тот же самый код без ошибки!
ASCII-код и атрибут биты 2 - 7 зарезервированы
Раздел: Рефераты по информатике, программированию
Тип: дипломная работа Просмотров: 5114 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Все работы, похожие на Дипломная работа: Корректирующие коды (11629)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150370)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru