Коррекция ошибок при передаче данных 10 класс семакин конспект урока

Слайд 1

Коррекция ошибок при передаче данных

Слайд 2

Символ Двоичный код Кодовое слово 0 1 2 3 4 5 6 7 8 9 Помехоустойчивый код Хемминга основные понятия – кодовое слово

Слайд 3

Символ Двоичный код Кодовое слово 0 0000 0000 1 0001 0001 2 0010 0010 3 0011 0011 4 0100 0100 5 0101 0101 6 0110 0110 7 0111 0111 8 1000 1000 9 1001 1001 Код Хемминга основные понятия – кодовое слово

Слайд 4

Символ Двоичный код Кодовое слово 0 0000 0000 000 1 0001 0001 111 2 0010 0010 110 3 0011 0011 001 4 0100 0100 101 5 0101 0101 010 6 0110 0110 011 7 0111 0111 100 8 1000 1000 011 9 1001 1001 100 Код Хемминга основные понятия – кодовое слово

Слайд 5

Код Хемминга основные понятия – расстояние между двумя словами (количество несовпадений в цифрах) Символ Двоичный код Кодовое слово 0 0000 0000 000 4 1 0001 0001 111 3 2 0010 0010 110 4 3 0011 0011 001 ? 4 0100 0100 101 ? 5 0101 0101 010 3 6 0110 0110 011 ? 7 0111 0111 100 ? 8 1000 1000 011 4 9 1001 1001 100

Слайд 6

Код Хемминга основные понятия – расстояние между двумя словами (количество несовпадений в цифрах) Символ Двоичный код Кодовое слово 0 0000 0000 000 4 1 0001 0001 111 3 2 0010 0010 110 4 3 0011 0011 001 4 4 0100 0100 101 4 5 0101 0101 010 3 6 0110 0110 011 ? 7 0111 0111 100 ? 8 1000 1000 011 4 9 1001 1001 100

Слайд 7

Код Хемминга основные понятия – расстояние между двумя словами (количество несовпадений в цифрах) Символ Двоичный код Кодовое слово 0 0000 0000 000 4 1 0001 0001 111 3 2 0010 0010 110 4 3 0011 0011 001 4 4 0100 0100 101 4 5 0101 0101 010 3 6 0110 0110 011 4 7 0111 0111 100 7 8 1000 1000 011 4 9 1001 1001 100

Слайд 8

АЛГОРИТМ ПОИСКА ПОМЕХ Разделить полученное сообщение на 7-битовые слова 1000011 1001111 0110010 0100101 Сравниваем каждую группу с кодовым словом из кода Хемминга

Слайд 9

1000011 Если полученное слово совпало с кодовым словом в таблице, то сообщение прошло без ошибок Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 10

1001111 Если в таблице есть слово, расстояние от которого до полученного равно 1, то полученное слово заменяется на ближайшее к нему из таблицы Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 11

0110010 Если в таблице есть слова, расстояние от которого до полученного равно 1, то полученное слово заменяется на ближайшее к нему из таблицы Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 12

0100101 Если полученное слово совпало с кодовым словом в таблице, то сообщение прошло без ошибок Символ Кодовое слово 0 0000 000 1 0001 111 2 0010 110 3 0011 001 4 0100 101 5 0101 010 6 0110 011 7 0111 100 8 1000 011 9 1001 100

Слайд 13

Следовательно, передано сообщение: 8164. Если в таблице есть слова, расстояние от которого до полученного равно 2, тогда слово исправить нельзя.

Слайд 14

Практическая часть Реализуйте программу Hemming в системе программирования на Паскале (смотрите стр. 93 — 96). Выполните описанные тесты. ДОМАШНЕЕ ЗАДАНИЕ. § 1.5.3

Источник

Дисциплина: ТЕХНОЛОГИИ ФИЗИЧЕСКОГО УРОВНЯ
ПЕРЕДАЧИ ДАННЫХ

Занятие №10

Методы обнаружения и коррекции ошибок
при передаче информации в компьютерных сетях.

ПЛАН ЗАНЯТИЯ:

1. Обнаружение и коррекция ошибок

2. Методы обнаружения ошибок

3. Методы коррекции ошибок

4. Вопросы

Обнаружение и коррекция ошибок

Надежную передачу
информации обеспечивают различные методы. Основной

принцип работы протоколов, которые
обеспечивают надежность передачи информации —

повторная передача искаженных или потерянных
пакетов.

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

Еще одним, более
эффективным подходом, чем повторная передача пакетов,

является использование самокорректирующихся
кодов, которые позволяют не только

обнаруживать, но и исправлять ошибки в
принятом кадре.

Методы обнаружения ошибок

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

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

вероятности о достоверности принятых данных. В
сетях с коммутацией пакетов такой

единицей информации может быть PDU
любого уровня, для определенности будем

считать, что мы контролируем кадры.

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

или контрольной последовательностью
кадра (Frame Check Sequence, FCS).

Контрольная сумма
вычисляется как функция от основной информации, причем не

обязательно путем суммирования.

Принимающая
сторона повторно вычисляет контрольную сумму кадра по

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

передающей стороной, делает вывод о том,
что данные были переданы через сеть

корректно.

Рассмотрим
несколько распространенных алгоритмов вычисления контрольной

суммы, отличающихся вычислительной
сложностью и способностью обнаруживать

ошибки в данных.

Контроль по
паритету.

Контроль по
паритету представляет собой наиболее простой метод контроля

данных. В то же время это наименее мощный
алгоритм контроля, так как с его помощью

можно обнаруживать только одиночные
ошибки в проверяемых данных.

Метод заключается в
суммировании по модулю 2 всех битов контролируемой информации.

Нетрудно заметить, что для информации,
состоящей из нечетного числа единиц,

контрольная сумма всегда равна 1, а при четном
числе единиц — 0.

Например, для данных 100101011 результатом контрольного суммирования будет

значение 1. Результат суммирования также
представляет собой один дополнительный бит

данных, который пересылается вместе с
контролируемой информацией. При искажении в

процессе пересылки любого одного бита исходных
данных (или контрольного разряда)

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

говорит об ошибке.

Однако двойная
ошибка, например 110101010, будет неверно принята за

корректные данные.
Поэтому контроль по паритету применяется к небольшим порциям

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

метода 1/8.

Метод редко
используется в компьютерных сетях из-за значительной

избыточности и невысоких диагностических
возможностей.

Вертикальный и
горизонтальный контроль по паритету

Вертикальный и
горизонтальный контроль по паритету представляет собой

модификацию описанного метода. Его отличие
состоит в том, что исходные данные

рассматриваются в виде матрицы, строки
которой составляют байты данных.

Контрольный разряд
подсчитывается отдельно для каждой строки и для каждого столбца

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

обладает еще большей избыточностью. На
практике этот метод сейчас также почти не

применяется при передаче информации по сети.

Циклический избыточный контроль

Циклический
избыточный контроль (Cyclic Redundancy Check, CRC) является в

настоящее время наиболее популярным методом
контроля в вычислительных сетях (и не

только в сетях, например, этот метод широко
применяется при записи данных на гибкие и

жесткие диски).

Метод основан на
представлении исходных данных в виде одного многоразрядного

двоичного числа.

Например, кадр стандарта Ethernet, состоящий из 1024 байт, рассматривается как

одно число, состоящее из 8192 бит. Контрольной
информацией считается остаток от

деления этого числа на известный делитель R.
Обычно в качестве делителя выбирается

семнадцати- или тридцатитрехразрядное число,
чтобы остаток от деления имел длину 16

разрядов (2 байт) или 32 разряда (4 байт).

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

Если остаток от
деления на R равен нулю, то делается вывод об отсутствии ошибок в полученном
кадре, в противном случае кадр считается искаженным.

Этот метод
обладает более высокой вычислительной сложностью, но его

диагностические возможности гораздо выше, чем
у методов контроля по паритету.

Этот метод
позволяет обнаруживать все одиночные ошибки, двойные ошибки и

ошибки в нечетном числе битов.

Метод обладает
также невысокой степенью избыточности. Например, для кадра

Ethernet размером 1024 байт контрольная
информация длиной 4 байт составляет только

0,4 %.

Методы коррекции ошибок

Техника
кодирования, которая позволяет приемнику не только понять, что

присланные данные содержат ошибки, но и
исправить их, называется прямой

коррекцией ошибок — (Forward Error Correction, FEC).

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

При применении
любого избыточного кода не все комбинации кодов являются

разрешенными. Например, контроль по паритету
делает разрешенными только половину

кодов.

Если мы
контролируем три информационных бита, то разрешенными 4-битными

кодами с дополнением до нечетного количества
единиц будут:

000 1, 001 0, 010 0, 011 1, 100
0, 101 1, 110 1, 111 0

То есть всего 8 кодов из 16 возможных.

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

исправления ошибок, нужно знать так
называемое расстояние Хемминга между

разрешенными комбинациями кода.

Расстоянием
Хемминга называется минимальное число битовых разрядов, в

которых отличается любая пара разрешенных
кодов.

Для схем контроля
по паритету расстояние Хемминга равно 2.

Можно доказать, что если мы сконструировали
избыточный код с расстоянием

Хемминга, равным N, то
такой код будет в состоянии распознавать (N-1)-кратные
ошибки

и исправлять (N-1)/2-кратные
ошибки.

Так как коды с
контролем по паритету имеют расстояние Хемминга, равное 2, то

они могут только обнаруживать однократные
ошибки и не могут исправлять ошибки.

Коды Хемминга
эффективно обнаруживают и исправляют изолированные ошибки,

то есть отдельные искаженные биты,
которые разделены большим количеством

корректных битов.

Однако при
появлении длинной последовательности искаженных битов (пульсации

ошибок) коды Хемминга не работают.

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

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

этом методе задействуется решетчатая
диаграмма, то такие коды еще называют

решетчатыми.

Эти коды
используются не только в беспроводных каналах, но и в модемах.

Методы прямой коррекции ошибок особенно
эффективны для технологий

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

данных в случае их искажения.

Вопросы
:

1. Что называется контрольной
последовательностью кадра?

2. Что представляет собой контроль по
паритету?

3. Что представляет собой вертикальный и
горизонтальный контроль по паритету?

4. Что представляет собой циклический избыточный
контроль?

5. Что называется прямой коррекцией ошибок?

6. Что называется расстоянием Хемминга?

7. Какие коды называются решетчатыми?

8. Где используются решетчатые коды?

Источник

Обновлено: 28.01.2023

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

Ну а теперь рассмотрим два случая ошибок в одном из битов посылки, например, в бите 7 (1 вместо 0) и в бите 5 (0 вместо 1). Просуммируем коды позиций ненулевых бит еще раз.

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

С1 = М1 + М2 + М4
С2 = М1 + М3 + М4
С3 = М2 + М3 + М4

С11 = С1 + М4 + М2 + М1
С12 = С2 + М4 + М3 + М1
С13 = С3 + М4 + М3 + М2

Результат вычисления интерпретируется следующим образом.

Описанная схема легко переносится на любое число n и М.

Число возможных кодовых комбинаций М помехоустойчивого кода делится на n классов, где N — число разрешенных кодов. Разделение на классы осуществляется так, чтобы в каждый класс вошел один разрешенный код и ближайшие к нему (по расстоянию Хэмминга) запрещенные коды. В процессе приема данных определяется, к какому классу принадлежит пришедший код. Если код принят с ошибкой, он заменяется ближайшим разрешенным кодом. При этом предполагается, что кратность ошибки не более q_m.

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

откуда следует (логарифм по основанию 2), что k может принимать значения 0, 1, 4, 11, 26, 57 и т.д., это и определяет соответствующие коды Хэмминга (3,1); (7,4); (15,11); (31,26); (63,57) и т.д.

Циклические коды

Обобщением кодов Хэмминга являются циклические коды BCH (Bose-Chadhuri-Hocquenghem). Это коды с широким выбором длины и возможностей исправления ошибок. Циклические коды характеризуются полиномом g(x) степени n-k, g(x) = 1 + g₁x + g₂x 2 + . + x n-k . g(x) называется порождающим многочленом циклического кода. Если многочлен g(x) n-k и является делителем многочлена x n + 1, то код C(g(x)) является линейным циклическим (n,k)-кодом. Число циклических n-разрядных кодов равно числу делителей многочлена x n + 1.

При кодировании слова все кодовые слова кратны g(x). g(x) определяется на основе сомножителей полинома x n +1 как:

Например, если n=7 (x 7 +1), его сомножители (1 + x + x 3 )(1 + x + x 2 + x 4 ), а g(x) = 1+x + x 3 .

Увеличивая разность N-M, можно не только нарастить число исправляемых бит m, но открыть возможность обнаружить множественные ошибки. В таблице 2.8.2 приведен процент обнаруживаемых множественных ошибок в зависимости от M и N-M.

Другой блочный метод предполагает «продольное и поперечное» контрольное суммирование предаваемого блока. Блок при этом представляется в виде N строк и M столбцов. Вычисляется биты четности для всех строк и всех столбцов, в результате получается два кода, соответственно длиной N и M бит. На принимающей стороне биты четности для строк и столбцов вычисляются повторно и сравниваются с присланными. При выявлении отличия в бите i кода битов четности строк и бите j — кода столбцов, позиция неверного бита оказывается определенной (i,j). Понятно, что если выявится два и более неверных битов в контрольных кодах строк и столбцов, задача коррекции становится неразрешимой. Уязвим этот метод и для двойных ошибок, когда сбой был, а контрольные коды остались корректными.

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

Линейные блочные коды

Если , то H[A T I] =

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Дисциплина: ТЕХНОЛОГИИ ФИЗИЧЕСКОГО УРОВНЯ ПЕРЕДАЧИ ДАННЫХ

Методы обнаружения и коррекции ошибок при передаче информации в компьютерных сетях.

1. Обнаружение и коррекция ошибок

2. Методы обнаружения ошибок

3. Методы коррекции ошибок

Обнаружение и коррекция ошибок

Надежную передачу информации обеспечивают различные методы. Основной

принцип работы протоколов, которые обеспечивают надежность передачи информации —

повторная передача искаженных или потерянных пакетов.

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

Еще одним, более эффективным подходом, чем повторная передача пакетов,

является использование самокорректирующихся кодов, которые позволяют не только

обнаруживать, но и исправлять ошибки в принятом кадре.

Методы обнаружения ошибок

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

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

вероятности о достоверности принятых данных. В сетях с коммутацией пакетов такой

единицей информации может быть PDU любого уровня, для определенности будем

считать, что мы контролируем кадры.

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

или контрольной последовательностью кадра (Frame Check Sequence, FCS).

Контрольная сумма вычисляется как функция от основной информации, причем не

обязательно путем суммирования.

Принимающая сторона повторно вычисляет контрольную сумму кадра по

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

передающей стороной, делает вывод о том, что данные были переданы через сеть

Рассмотрим несколько распространенных алгоритмов вычисления контрольной

суммы, отличающихся вычислительной сложностью и способностью обнаруживать

ошибки в данных.

Контроль по паритету.

Контроль по паритету представляет собой наиболее простой метод контроля

данных. В то же время это наименее мощный алгоритм контроля, так как с его помощью

можно обнаруживать только одиночные ошибки в проверяемых данных.

Метод заключается в суммировании по модулю 2 всех битов контролируемой информации.

Нетрудно заметить, что для информации, состоящей из нечетного числа единиц,

контрольная сумма всегда равна 1, а при четном числе единиц — 0.

Например, для данных 100101011 результатом контрольного суммирования будет

значение 1. Результат суммирования также представляет собой один дополнительный бит

данных, который пересылается вместе с контролируемой информацией. При искажении в

процессе пересылки любого одного бита исходных данных (или контрольного разряда)

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

говорит об ошибке.

Однако двойная ошибка, например 110101010, будет неверно принята за

корректные данные . Поэтому контроль по паритету применяется к небольшим порциям

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

Метод редко используется в компьютерных сетях из-за значительной

избыточности и невысоких диагностических возможностей.

Вертикальный и горизонтальный контроль по паритету

Вертикальный и горизонтальный контроль по паритету представляет собой

модификацию описанного метода. Его отличие состоит в том, что исходные данные

рассматриваются в виде матрицы, строки которой составляют байты данных.

Контрольный разряд подсчитывается отдельно для каждой строки и для каждого столбца

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

обладает еще большей избыточностью. На практике этот метод сейчас также почти не

применяется при передаче информации по сети.

Циклический избыточный контроль

Циклический избыточный контроль (Cyclic Redundancy Check, CRC) является в

настоящее время наиболее популярным методом контроля в вычислительных сетях (и не

только в сетях, например, этот метод широко применяется при записи данных на гибкие и

Метод основан на представлении исходных данных в виде одного многоразрядного

Например, кадр стандарта Ethernet, состоящий из 1024 байт, рассматривается как

одно число, состоящее из 8192 бит. Контрольной информацией считается остаток от

деления этого числа на известный делитель R. Обычно в качестве делителя выбирается

семнадцати- или тридцатитрехразрядное число, чтобы остаток от деления имел длину 16

разрядов (2 байт) или 32 разряда (4 байт).

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

Если остаток от деления на R равен нулю, то делается вывод об отсутствии ошибок в полученном кадре, в противном случае кадр считается искаженным.

Этот метод обладает более высокой вычислительной сложностью, но его

диагностические возможности гораздо выше, чем у методов контроля по паритету.

Этот метод позволяет обнаруживать все одиночные ошибки, двойные ошибки и

ошибки в нечетном числе битов.

Метод обладает также невысокой степенью избыточности. Например, для кадра

Ethernet размером 1024 байт контрольная информация длиной 4 байт составляет только

Методы коррекции ошибок

Техника кодирования, которая позволяет приемнику не только понять, что

коррекцией ошибок — (Forward Error Correction, FEC).

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

При применении любого избыточного кода не все комбинации кодов являются

разрешенными. Например, контроль по паритету делает разрешенными только половину

Если мы контролируем три информационных бита, то разрешенными 4-битными

кодами с дополнением до нечетного количества единиц будут:

000 1, 001 0, 010 0, 011 1, 100 0, 101 1, 110 1, 111 0

То есть всего 8 кодов из 16 возможных.

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

исправления ошибок, нужно знать так называемое расстояние Хемминга между

разрешенными комбинациями кода.

Расстоянием Хемминга называется минимальное число битовых разрядов, в

которых отличается любая пара разрешенных кодов.

Для схем контроля по паритету расстояние Хемминга равно 2.

Можно доказать, что если мы сконструировали избыточный код с расстоянием

Хемминга, равным N , то такой код будет в состоянии распознавать ( N -1)-кратные ошибки

и исправлять ( N -1)/2-кратные ошибки.

Так как коды с контролем по паритету имеют расстояние Хемминга, равное 2, то

они могут только обнаруживать однократные ошибки и не могут исправлять ошибки.

Коды Хемминга эффективно обнаруживают и исправляют изолированные ошибки,

то есть отдельные искаженные биты, которые разделены большим количеством

Однако при появлении длинной последовательности искаженных битов (пульсации

ошибок) коды Хемминга не работают.

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

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

этом методе задействуется решетчатая диаграмма, то такие коды еще называют

решетчатыми.

Эти коды используются не только в беспроводных каналах, но и в модемах.

Методы прямой коррекции ошибок особенно эффективны для технологий

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

данных в случае их искажения.

1. Что называется контрольной последовательностью кадра?

2. Что представляет собой контроль по паритету?

3. Что представляет собой вертикальный и горизонтальный контроль по паритету?

Презентация: Коррекция ошибок при передаче данных

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

Аннотация к презентации

Содержание

Коррекция ошибок при передаче данных

Слайд 2

Помехоустойчивый код Хеммингаосновные понятия – кодовое слово

Слайд 3

Код Хеммингаосновные понятия – кодовое слово

Слайд 4

Код Хеммингаосновные понятия – кодовое слово

Слайд 5

Код Хеммингаосновные понятия – расстояние между двумя словами(количество несовпадений в цифрах)

Слайд 6

Слайд 7

Слайд 8

Слайд 9

Слайд 10

1001111 Если в таблице есть слово, расстояние от которого до полученного равно 1, то полученное слово заменяется на ближайшее к нему из таблицы

Слайд 11

0110010 Если в таблице есть слова, расстояние от которого до полученного равно 1, то полученное слово заменяется на ближайшее к нему из таблицы

Слайд 12

Слайд 13

Слайд 14

Практическая часть

Реализуйте программу Hemming в системе программирования на Паскале (смотрите стр. 93 — 96). Выполните описанные тесты. ДОМАШНЕЕ ЗАДАНИЕ. § 1.5.3

Теоретический материал для самостоятельного изучения:

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

Обработка информации

Обработка информации — это целенаправленный процесс изменения формы ее представления или содержания.

Из курса информатики основной школы вам известно, что существует два различных типа обработки информации:

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

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

— структурирование — организация информации по некоторому правилу, связывающему ее в единое целое (например, сортировка);

— поиск и отбор информации, требуемой для решения некоторой задачи, из информационного массива (например, поиск в словаре).

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

Исходные данные — это информация, которая подвергается обработке.

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

Исполнитель — тот объект, который осуществляет обработку. Это может быть человек или компьютер. При этом человек, как правило, является неформальным, творчески действующим исполнителем. Компьютер же способен работать только в строгом соответствии с правилами, т.е. является формальным исполнителем обработки информации.

Рассмотрим отдельные процессы обработки информации более подробно.

Кодирование информации

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

Код — это система условных обозначений (кодовых слов), используемых для представления информации.

Кодовая таблица — это совокупность используемых кодовых слов и их значений.

Нам уже знакомы примеры равномерных двоичных кодов — пятиразрядный код Бодо и восьмиразрядный код ASCII.

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

При использовании неравномерных кодов важно понимать, сколько различных кодовых слов они позволяют построить.

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

Нас интересует семибуквенная последовательность, т. е.

Если бы у нас не было условия, что в ней должны содержаться ровно пять букв А, то для первого символа было бы 4 варианта, для второго — тоже 4, и т. д.

Тогда мы получили бы: 4 · 4 · 4 · 4 · 4 · 4 · 4 = 16384 варианта.

Теперь вернемся к имеющемуся условию и заполним пять первых мест буквой А. Получим:

Так как на 6-м и 7-м местах могут стоять любые из трех оставшихся букв B, C, D, то всего существует 9 (3 · 3) вариантов последовательностей.

Но ведь буквы А могут находиться на любых пяти из семи имеющихся позиций. А сколько таких вариантов всего?

Префиксный код — код со словом переменной длины, обладающий тем свойством, что никакое его кодовое слово не может быть началом другого (более длинного) кодового слова.

Код, состоящий из слов 0, 10 и 11, является префиксным.
Код, состоящий из слов 0, 10, 11 и 100, не является префиксным.

Также достаточным условием однозначного декодирования неравномерного код является обратное условие Фано. В нем требуется, чтобы никакой код не был окончанием другого (более длинного) кода.

Пример 2. Двоичные коды для 5 букв латинского алфавита представлены в таблице:

Можно заметить, что для заданных кодов не выполняется прямое условие Фано:

B=01, E=011, и D=10, C=100.

А вот обратное условие Фано выполняется: никакое кодовое слово не является окончанием другого. Следовательно, имеющуюся строку нужно декодировать справа налево (с конца). Получим

01 10 100 011 000 = BDCEA

Для построения префиксных кодов удобно использовать бинарные деревья, в которых от каждого узла отходят только два ребра, помеченные цифрами 0 и 1.

Пример 3. Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются такие кодовые слова: А — 0, Б — 10, В — 110. Каким кодовым словом может быть закодирована буква Г? Если таких слов несколько, укажите кратчайшее из них.

Построим бинарное дерево:

Чтобы найти код символа, нужно пройти по стрелкам от корня дерева к нужному листу, выписывая метки стрелок, по которым мы переходим.

Определим положение букв А, Б и В на этом дереве, зная их коды. Получим:

Чтобы код был префиксным, ни один символ не должен лежать на пути от корня к другому символу. Уберем лишние стрелки:

На получившемся дереве можно определить подходящее расположение буквы Г и его код.

Поиск информации

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

Алгоритм поиска, в свою очередь, также зависит от способа организации данных.

Если данные никак не упорядочены, то мы имеем дело с неструктурированным набором данных. Для осуществления поиска в таком наборе применяется метод последовательного перебора.

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

— искомый элемент найден;

— просмотрен весь набор данных, но искомого элемента среди них не нашлось.

— искомый элемент оказался первым среди просматриваемых. Тогда просмотр всего один;

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

Одним из оптимальных алгоритмов поиска в структурированном наборе данных может быть метод половинного деления.

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

Пример 4. В последовательности чисел 61 87 180 201 208 230 290 345 367 389 456 478 523 567 590 требуется найти число 180.

Процесс поиска представлен на схеме:

Передача информации

Передача информации — это процесс распространения информации от источника к приемнику через определенный канал связи.

На рисунке представлена схема модели процесса передачи информации по техническим каналам связи, предложенная Клодом Шенноном.

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

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

В современных технических системах связи борьба с шумом (защита от шума) осуществляется по следующим двум направлениям:

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

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

Современные технические каналы связи обладают, перед ранее известными, целым рядом достоинств:

— высокая пропускная способность, обеспечиваемая свойствами используемых носителей;

— надёжность, связанная с использованием параллельных каналов связи;

— помехозащищённость, основанная на автоматических системах проверки целостности переданной информации;

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

Объём переданной информации I вычисляется по формуле:

где v — пропускная способность канала (в битах в секунду), а t — время передачи.

Рассмотрим пример решения задачи, имеющей отношение к процессу передачи информации.

Пример 5. Документ объемом 10 Мбайт можно передать с одного компьютера на другой двумя способами.

А. Передать по каналу связи без использования архиватора.

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

Какой способ быстрее и насколько, если:

— средняя скорость передачи данных по каналу связи составляет 2 18 бит/с;

— объем сжатого архиватором документа равен 25% от исходного объема;

— время, требуемое на сжатие документа — 5 секунд, на распаковку — 3 секунды?

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

Рассмотрим вариант А. Длительность передачи информации в этом случае составит:

Рассмотрим вариант Б. Длительность передачи информации в этом случае составит:

Итак, вариант Б быстрее на 232 с.

Хранение информации

Сохранить информацию — значит тем или иным способом зафиксировать её на некотором носителе.

Носитель информации — это материальная среда, используемая для записи и хранения информации.

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

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

Виды внешних носителей менялись со временем: в древности это были камень, дерево, папирус, кожа и др. Долгие годы основным носителем информации была бумага. Развитие компьютерной техники привело к созданию магнитных (магнитная лента, гибкий магнитный диск, жёсткий магнитный диск), оптических (CD, DVD, BD) и других современных носителей информации.

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

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

Читайте также:

Конспект урока 2 класс словарный диктант

Природа в классе 1 класс перспектива конспект урока

Конспект урока в инклюзивном классе по русскому языку 2 класс

Конспект занятия по фцкм 1 мл группа по дороге в детский сад

Конспект по обучению грамоте в подготовительной группе по теме транспорт

Источник

Презентация на тему «Коррекция ошибок при передаче данных» 10 класс

Скачать презентацию (0.37 Мб)
18 загрузок
0.0 оценка

Ваша оценка презентации

Оцените презентацию по шкале от 1 до 5 баллов

Аннотация к презентации

Посмотреть и скачать презентацию по теме «Коррекция ошибок при передаче данных» по информатике, включающую в себя 14 слайдов. Скачать файл презентации 0.37 Мб. Для учеников 10 класса. Большой выбор учебных powerpoint презентаций по информатике

Формат

pptx (powerpoint)
Количество слайдов

14
Аудитория
Слова
Конспект

Отсутствует

Содержание

Слайд 1

Коррекция ошибок при передаче данных
Слайд 2

Помехоустойчивый код Хеммингаосновные понятия – кодовое слово
Слайд 3

Код Хеммингаосновные понятия – кодовое слово
Слайд 4

Код Хеммингаосновные понятия – кодовое слово
Слайд 5

Код Хеммингаосновные понятия – расстояние между двумя словами(количество несовпадений в цифрах)
Слайд 6
Слайд 7
Слайд 8

АЛГОРИТМ ПОИСКА ПОМЕХ
Разделить полученное сообщение на 7-битовые слова
1000011 1001111 0110010 0100101
Сравниваем каждую группу с кодовым словом из кода Хемминга
Слайд 9

1000011
Если полученное слово совпало с кодовым словом в таблице, то сообщение прошло без ошибок
Слайд 10

1001111
Если в таблице есть слово, расстояние от которого до полученного равно 1, то полученное слово заменяется на ближайшее к нему из таблицы
Слайд 11

0110010
Если в таблице есть слова, расстояние от которого до полученного равно 1, то полученное слово заменяется на ближайшее к нему из таблицы
Слайд 12

0100101
Если полученное слово совпало с кодовым словом в таблице, то сообщение прошло без ошибок
Слайд 13

Следовательно, передано сообщение: 8164.

Если в таблице есть слова, расстояние от которого до полученного равно 2, тогда слово исправить нельзя.
Слайд 14

Практическая часть

Реализуйте программу Hemming в системе программирования на Паскале (смотрите стр. 93 — 96). Выполните описанные тесты.
ДОМАШНЕЕ ЗАДАНИЕ. § 1.5.3

Посмотреть все слайды

Сообщить об ошибке

Информатика — Все разработки учителей

К учебнику: Информатика. 10 класс. Углубленный уровень. В 2 ч. Семакин И.Г., Шеина Т.Ю., Шестакова Л.В. М.: 2014 — Ч.1 — 184с., Ч.2 — 232с.

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

Показывать:

10 класс

Все классы
Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
СУЗ
ВУЗ
Прочее

Информатика. 10 класс. Углубленный уровень. В 2 ч. Семакин И.Г., Шеина Т.Ю., Шестакова Л.В. М.: 2014 — Ч.1 — 184с., Ч.2 — 232с.

Все учебники
Информатика (базовый уровень) (в 2 частях) ООО «БИНОМ. Лаборатория знаний» Под ред. Макаровой Н.В. 10–11 классы 2017
Информатика (базовый уровень) ООО «БИНОМ. Лаборатория знаний» Угринович Н.Д. 10 класс 2018. — 288 с.
Информатика и ИКТ. 10 класс. Базовый и профильный уровни. Гейн А.Г. и др. М.: 2012. — 272 с.
Информатика. 10 класс. Углубленный уровень. В 2 ч. Поляков К.Ю., Еремин Е.А. М.: 2013 — Ч.1 — 344с., Ч.2 — 304с.
Информатика. 10 класс. Углубленный уровень. В 2 ч. Семакин И.Г., Шеина Т.Ю., Шестакова Л.В. М.: 2014 — Ч.1 — 184с., Ч.2 — 232с.
Информатика. Базовый уровень ООО «БИНОМ. Лаборатория знаний» Босова Л.Л., Босова А.Ю. 10 класс 2019
Информатика. Базовый уровень: учебник для 10 класса, Семакин И.Г., Хеннер Е.К., М.: БИНОМ. Лаборатория знаний, 2016. – 264 с.
Информатика. Базовый уровень: учебник для 10 класса. Семакин И. Г. и др. — М.: 2013 — 264 с.
Информатика. Углубленный уровень: учебник для 10 класса, Калинин И.А., Самылкина Н.Н., Изд. «БИНОМ. Лаборатория знаний» 2013, 256 с.

Все темы

Все темы
ЧАСТЬ 1.
От авторов
Глава 1. Теоретические основы информатики
1.1. Информатика и информация
1.2. Измерение информации
1.2.1. Алфавитный подход к измерению информации
1.2.2. Содержательный подход к измерению информации
1.2.3. Вероятность и информация
1.3. Системы счисления
1.3.1. Основные понятия систем счисления
1.3.2. Перевод десятичных чисел в другие системы счисления
1.3.3. Автоматизация перевода чисел из системы в систему
1.3.4. Смешанные системы счисления
1.3.5. Арифметика в позиционных системах счисления
1.4. Кодирование
1.4.1. Информация и сигналы
1.4.2. Кодирование текстовой информации
1.4.3. Кодирование изображения
1.4.4. Кодирование звука
1.4.5. Сжатие двоичного кода
1.5. Информационные процессы
1.5.1. Хранение информации
1.5.2. Передача информации
1.5.3. Коррекция ошибок при передаче данных
1.5.4. Обработка информации
1.6. Логические основы обработки информации
1.6.1. Логика и логические операции
1.6.2. Логические формулы и функции
1.6.3. Логические формулы и логические схемы
1.6.4. Методы решения логических задач
1.6.5. Логические функции на области числовых значений
1.7. Алгоритмы обработки информации
1.7.1. Определение, свойства и описание алгоритма
1.7.2. Алгоритмическая машина Тьюринга
1.7.3. Алгоритмическая машина Поста
1.7.4. Этапы алгоритмического решения задачи
1.7.5. Алгоритмы поиска данных
1.7.6. Программирование поиска
1.7.7. Алгоритмы сортировки данных
ЧАСТЬ 2.
Глава 2. Компьютер
2.1. Логические основы компьютера
2.1.1. Логические элементы и переключательные схемы
2.1.2. Логические схемы элементов компьютера
2.2. Эволюция устройства вычислительной машины
2.3. Смена поколений ЭВМ
2.4. Обработка чисел в компьютере
2.4.1. Представление и обработка целых чисел
2.4.2. Представление и обработка вещественных чисел
2.5. Персональный компьютер и его устройство
2.5.1. История и архитектура персональных компьютеров
2.5.2. Микропроцессор: основные элементы и характеристики
2.5.3. Системная (материнская) плата
2.5.4. Системная (внутренняя) память компьютера
2.5.5. Долговременная (внешняя) память компьютера
2.5.6. Устройства ввода и вывода информации
2.6. Программное обеспечение ПК
2.6.1. Виды программного обеспечения
О профессиях: системный администратор
2.6.2. Функции операционной системы
2.6.3. Операционные системы для ПК
Глава 3. Информационные технологии
3.1. Технологии обработки текстов
3.1.1. Текстовые редакторы и процессоры
3.1.2. Специальные тексты
3.1.3. Издательские системы
3.2. Технологии обработки изображения и звука
3.2.1. Основы графических технологий
3.2.2. Трехмерная графика
3.2.3. Технологии работы с цифровым видео
3.2.4. Технологии работы со звуком
3.2.5. Мультимедиа
3.2.6. Использование мультимедийных эффектов в презентации
3.3. Технологии табличных вычислений
3.3.1. Структура электронной таблицы и типы данных
3.3.2. Встроенные функции. Передача данных между листами
3.3.3. Деловая графика
3.3.4. Фильтрация данных
3.3.5. Поиск решения и подбор параметра
Глава 4. Компьютерные телекоммуникации
4.1. Организация локальных компьютерных сетей
4.1.1. Назначение и состав локальных сетей
4.1.2. Классы и топологии локальных сетей
О профессиях: администратор локальной сети
4.2. Глобальные компьютерные сети
4.2.1. История и классификация глобальных сетей
4.2.2. Структура Интернета. Сетевая модель DoD
4.2.3. Основные службы Интернета
4.3. Основы сайтостроения
4.3.1. Способы создания сайтов. Понятие о языке HTML
4.3.2. Оформление и разработка сайта
О профессиях: web-дизайнер и другие профессии
4.3.3. Создание гиперссылок и таблиц.
Браузеры

Презентация по информатике …

15.10.2021 09:20
232

5

Презентация по информатике …

15.10.2021 09:21
180

0

…

15.10.2021 09:25
132

1

Цели: научить определять информационный объем сообщения с помощью алфавитного подхода к измерению информации; научить определять мощность алфавита, с помощью которого создано сообщение; научить определять информационный вес одного символа из алфавита;&nbs …

02.11.2021 11:45
537

11

Презентация к уроку «Измерение информации. Алфавитный подход» …

02.11.2021 12:14
242

4

Задание №1 – Называйте вещи своими именами

Задание №2 – Век за веком

Задание №3 — Знаменитые аппараты

Задание №4 — География изобретений

Задание №5 – Нобелевские лауреаты …

07.12.2021 13:10
174

0

Рабочая программа учебного предмета «Информатика» на уровне среднего общего образования составлена в соответствии с требованиями ФГОС СОО, ориентирована на использование учебника «Информатика. Углубленный уровень: учебник для 10 класса: в 2ч./И.Г. Семакин, Т.Ю. Шеина, Л.В. …

26.12.2021 23:40
208

1

Технологическая карта проекта кружковой работы

…

05.04.2022 21:10
148

0

Цель: обобщить и применить для решения задач знания о способах перевода чисел; развитие познавательного интереса, творческой активности учащихся.

Задачи:

Обучающая:

— повторение и обобщение темы «системы счисления» …

04.09.2022 11:32
96

2

Контрольная работа за 1 полугодие для 10 класса по информатике по учебнику Семакина (углубленный уровень) …

12.12.2022 14:30
426

13

Источник

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

Большая часть протоколов канального уровня выполняет только первую задачу —
обнаружение ошибок, считая, что корректировать ошибки, то есть повторно
передавать данные, содержавшие искаженную информацию, должны протоколы верхних
уровней. Так работают такие популярные протоколы локальных сетей, как Ethernet,
Token Ring, FDDI и другие. Однако существуют протоколы канального уровня, например
LLC2 или LAP-B, которые самостоятельно решают задачу восстановления искаженных
или потерянных кадров.

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

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

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

Методы обнаружения ошибок

Все методы обнаружения ошибок основаны на передаче в составе кадра данных
служебной избыточной информации, по которой можно судить с некоторой степенью
вероятности о достоверности принятых данных. Эту служебную информацию принято
называть контрольной суммой или (последовательностью
контроля кадра — Frame Check Sequence, FCS). Контрольная сумма вычисляется
как функция от основной информации, причем необязательно только путем суммирования.
Принимающая сторона повторно вычисляет контрольную сумму кадра по известному
алгоритму и в случае ее совпадения с контрольной суммой, вычисленной передающей
стороной, делает вывод о том, что данные были переданы через сеть корректно.

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

Контроль по паритету представляет собой наиболее простой метод контроля данных. В то же
время это наименее мощный алгоритм контроля, так как с его помощью можно
обнаружить только одиночные ошибки в проверяемых данных. Метод заключается в
суммировании по модулю 2 всех бит контролируемой информации. Например, для
данных 100101011 результатом контрольного суммирования будет значение 1.
Результат суммирования также представляет собой один бит данных, который
пересылается вместе с контролируемой информацией. При искажении при пересылке
любого одного бита исходных данных (или контрольного разряда) результат суммирования
будет отличаться от принятого контрольного разряда, что говорит об ошибке.
Однако двойная ошибка, например 110101010, будет неверно принята за корректные
данные. Поэтому контроль по паритету применяется к небольшим порциям данных,
как правило, к каждому байту, что дает коэффициент избыточности для этого
метода 1/8. Метод редко применяется в вычислительных сетях из-за его большой
избыточности и невысоких диагностических способностей.

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

Циклический избыточный контроль (Cyclic Redundancy Check, CRC) является в настоящее время наиболее
популярным методом контроля в вычислительных сетях (и не только в сетях,
например, этот метод широко применяется при записи данных на диски и дискеты).
Метод основан на рассмотрении исходных данных в виде одного многоразрядного
двоичного числа. Например, кадр стандарта Ethernet, состоящий из 1024 байт,
будет рассматриваться как одно число, состоящее из 8192 бит. В качестве
контрольной информации рассматривается остаток от деления этого числа на
известный делитель R. Обычно в качестве делителя выбирается семнадцати- или тридцати
трехразрядное число, чтобы остаток от деления имел длину 16 разрядов (2 байт)
или 32 разряда (4 байт). При получении кадра данных снова вычисляется остаток
от деления на тот же делитель R, но при этом к данным кадра добавляется и
содержащаяся в нем контрольная сумма. Если остаток от деления на R равен нулю¹ (¹ Существуетнесколько
модифицированная процедура вычисления остатка, приводящая к получению в случае
отсутствия ошибок известного ненулевого остатка, что является более надежным
показателем корректности.), то делается вывод об отсутствии ошибок в полученном
кадре, в противном случае кадр считается искаженным.

Этот метод обладает более высокой вычислительной сложностью, но его
диагностические возможности гораздо выше, чем у методов контроля по паритету.
Метод CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном
числе бит. Метод обладает также невысокой степенью избыточности. Например, для
кадра Ethernet размером в 1024 байт контрольная информация длиной в 4 байт
составляет только 0,4 %.

Методы восстановления искаженных и потерянных кадров

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

Существуют два подхода к организации процесса обмена квитанциями: с
простоями и с организацией «окна».

Метод с простоями (Idle Source) требует, чтобы источник, пославший кадр, ожидал получения квитанции
(положительной или отрицательной) от приемника и только после этого посылал
следующий кадр (или повторял искаженный). Если же квитанция не приходит в
течение тайм-аута, то кадр (или квитанция) считается утерянным и его передача
повторяется. На рис. 2.24, а видно, что в этом случае производительность обмена
данными существенно снижается, — хотя передатчик и мог бы послать следующий
кадр сразу же после отправки предыдущего, он обязан ждать прихода квитанции.
Снижение производительности этого метода коррекции особенно заметно на
низкоскоростных каналах связи, то есть в территориальных сетях.

Рис. 2.24. Методы восстановления искаженных и
потерянных кадров

Второй метод называется методом «скользящего окна» (sliding
window). В этом методе для повышения коэффициента использования линии
источнику разрешается передать некоторое количество кадров в непрерывном
режиме, то есть в максимально возможном для источника темпе, без получения на
эти кадры положительных ответных квитанций. (Далее, где это не искажает
существо рассматриваемого вопроса, положительные квитанции для краткости будут
называться просто «квитанциями».) Количество кадров, которые разрешается
передавать таким образом, называется размером окна. Рисунок 2.24, б
иллюстрирует данный метод для окна размером в W кадров.

В начальный момент, когда еще не послано ни одного кадра, окно определяет
диапазон кадров с номерами от 1 до W включительно. Источник начинает передавать
кадры и получать в ответ квитанции. Для простоты предположим, что квитанции
поступают в той же последовательности, что и кадры, которым они соответствуют.
В момент t₁ при получении первой квитанции К1 окно сдвигается
на одну позицию, определяя новый диапазон от 2 до (W+1).

Процессы отправки кадров и получения квитанций идут достаточно независимо
друг от друга. Рассмотрим произвольный момент времени tn, когда источник
получил квитанцию на кадр с номером n. Окно сдвинулось вправо и определило
диапазон разрешенных к передаче кадров от (n+1) до (W+n). Все множество кадров,
выходящих из источника, можно разделить на перечисленные ниже группы (рис.
2.24, б).

Кадры с номерами от 1 доп. уже были отправлены и квитанции на них
получены, то есть они находятся за пределами окна слева.
Кадры, начиная с номера (п+1) и кончая номером
(W+n), находятся в пределах окна и
потому могут быть отправлены не дожидаясь прихода какой-либо квитанции.
Этот диапазон может быть разделен еще на два поддиапазона:

кадры с номерами от (n+1) до
т, которые уже отправлены, но квитанции на них еще не получены;
кадры с номерами от m до
(W+n), которые пока не отправлены, хотя запрета на это нет.

Все кадры с номерами, большими или равными
(W+n+1), находятся за пределами окна
справа и поэтому пока не могут быть отправлены.

Перемещение окна вдоль последовательности номеров кадров показано на рис.
2.24, в. Здесь t₀ — исходный момент, t₁ и t_n —
моменты прихода квитанций на первый и n-й кадр соответственно. Каждый раз,
когда приходит квитанция, окно сдвигается влево, но его размер при этом не
меняется и остается равным W. Заметим, что хотя в данном примере размер окна в
процессе передачи остается постоянным, в реальных протоколах (например, TCP)
можно встретить варианты данного алгоритма с изменяющимся размером окна.

Итак, при отправке кадра с номером n источнику разрешается передать еще W-1
кадров до получения квитанции на кадр n, так что в сеть последним уйдет кадр с
номером (W+n-1). Если же за это время квитанция на кадр n так и не пришла, то
процесс передачи приостанавливается, и по истечении некоторого тайм-аута кадр n
(или квитанция на него) считается утерянным, и он передается снова.

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

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

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

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

Метод скользящего окна реализован во многих протоколах: LLC2, LAP-B, X.25,
TCP, Novell NCP Burst Mode.

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

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

Выбор тайм-аута зависит не от надежности сети, а от задержек передачи
кадров сетью.

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

Источник

Коррекция ошибок при передаче данных 10 класс семакин конспект урока

Аннотация к презентации

Содержание

Практическая часть

Презентация на тему «Коррекция ошибок при передаче данных» 10 класс

Комментарии

Аннотация к презентации

Содержание

Практическая часть

Похожие презентации

Категории

Информатика — Все разработки учителей

К учебнику: Информатика. 10 класс. Углубленный уровень. В 2 ч. Семакин И.Г., Шеина Т.Ю., Шестакова Л.В. М.: 2014 — Ч.1 — 184с., Ч.2 — 232с.

А вот еще интересные материалы: