Контроль ошибок

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

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

В системах связи возможны несколько стратегий борьбы с ошибками:

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

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

Современное развитие корректирующих кодов приписывают Ричарду Хэммингу с 1947 года^[1]. Описание кода Хэмминга появилось в статье Клода Шеннона «Математическая теория связи»^[2] и было обобщено Марселем Голеем^[3].

Стратегии исправления ошибок править

Упреждающая коррекция ошибок править

Упреждающая коррекция ошибок (также прямая коррекция ошибок, англ. Forward Error Correction, FEC) — техника помехоустойчивого кодирования и декодирования, позволяющая исправлять ошибки методом упреждения. Применяется для исправления сбоев и ошибок при передаче данных путём передачи избыточной служебной информации, на основе которой может быть восстановлено первоначальное содержание. На практике широко используется в сетях передачи данных, телекоммуникационных технологиях. Коды, обеспечивающие прямую коррекцию ошибок, требуют введения большей избыточности в передаваемые данные, чем коды, которые только обнаруживают ошибки.

Например, в спутниковом телевидении при передаче цифрового сигнала с FEC 7/8 передаётся восемь бит информации: 7 бит полезной информации и 1 контрольный бит^[4]; в DVB-S используется всего 5 видов: 1/2, 2/3, 3/4 (наиболее популярен), 5/6 и 7/8. При прочих равных условиях, можно утверждать, что чем ниже значение FEC, тем меньше пакетов допустимо потерять, и, следовательно, выше требуемое качество сигнала.

Техника прямой коррекции ошибок широко применяется в различных устройствах хранения данных — жёстких дисках, флеш-памяти, оперативной памяти. В частности, в серверных приложениях применяется ECC-память — оперативная память, способная распознавать и исправлять спонтанно возникшие ошибки.

Автоматический запрос повторной передачи править

Системы с автоматическим запросом повторной передачи (англ. Automatic Repeat Request, ARQ) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Идея запроса ARQ с остановками (англ. stop-and-wait ARQ) заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем, как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для полудуплексного канала связи. Его недостатком является низкая скорость из-за высоких накладных расходов на ожидание.

Для метода непрерывного запроса ARQ с возвратом (continuous ARQ with pullback) необходим полнодуплексный канал. Передача данных от передатчика к приемнику производится одновременно. В случае ошибки передача возобновляется, начиная с ошибочного блока (то есть передается ошибочный блок и все последующие).

При использовании метода непрерывного запроса ARQ с выборочным повторении (continuous ARQ with selective repeat) осуществляется передача только ошибочно принятых блоков данных.

Сетевое кодирование править

Раздел теории информации, изучающий вопрос оптимизации передачи данных по сети с использованием техник изменения пакетов данных на промежуточных узлах называют сетевым кодированием. Для объяснения принципов сетевого кодирования используют пример сети «бабочка», предложенной в первой работе по сетевому кодированию «Network information flow»^[5]. В отличие от статического сетевого кодирования, когда получателю известны все манипуляции, производимые с пакетом, также рассматривается вопрос о случайном сетевом кодировании, когда данная информация неизвестна. Авторство первых работ по данной тематике принадлежит Кёттеру, Кшишангу и Силве^[6]. Также данный подход называют сетевым кодированием со случайными коэффициентами — когда коэффициенты, под которыми начальные пакеты, передаваемые источником, войдут в результирующие пакеты, принимаемые получателем, с неизвестными коэффициентами, которые могут зависеть от текущей структуры сети и даже от случайных решений, принимаемых на промежуточных узлах. Для неслучайного сетевого кодирования можно использовать стандартные способы защиты от помех и искажений, используемых для простой передачи информации по сети.

Энергетический выигрыш править

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

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

Примечания править

↑ Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), The Mathematical Association of America, p. vii, ISBN 0-88385-023-0
↑ Shannon, C.E. (1948), "A Mathematical Theory of Communication", Bell System Technical Journal, p. 418, 27 (3): 379—423, doi:10.1002/j.1538-7305.1948.tb01338.x, hdl:10338.dmlcz/101429, PMID 9230594{{citation}}: Википедия:Обслуживание CS1 (location) (ссылка)
↑ Golay, Marcel J. E. (1949), "Notes on Digital Coding", Proc.I.R.E. (I.E.E.E.), p. 657, 37{{citation}}: Википедия:Обслуживание CS1 (location) (ссылка)
↑ Understanding Digital Television: An Introduction to Dvb Systems With … — Lars-Ingemar Lundström — Google Книги (неопр.). Дата обращения: 19 мая 2020. Архивировано 11 ноября 2021 года.
↑ Ahlswede, R.; Ning Cai; Li, S.-Y.R.; Yeung, R.W., «Network information flow», Information Theory, IEEE Transactions on, vol.46, no.4, pp.1204-1216, Jul 2000
↑
Статьи:
- Koetter R., Kschischang F.R. Coding for errors and erasures in random network coding// IEEE International Symposium on Information Theory. Proc.ISIT-07.-2007.- P. 791—795.
- Silva D., Kschischang F.R. Using rank-metric codes for error correction in random network coding // IEEE International Symposium on Information Theory. Proc. ISIT-07. — 2007.
- Koetter R., Kschischang F.R. Coding for errors and erasures in random network coding // IEEE Transactions on Information Theory. — 2008- V. IT-54, N.8. — P. 3579-3591.
- Silva D., Kschischang F.R., Koetter R. A Rank-Metric Approach to Error Control in Random Network Coding // IEEE Transactions on Information Theory.- 2008- V. IT-54, N. 9.- P.3951-3967.

Литература править

Имеется викиучебник по теме «Помехоустойчивое кодирование»

Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.
Clark, George C., Jr., and J. Bibb Cain. Error-Correction Coding for Digital Communications. New York: Plenum Press, 1981. ISBN 0-306-40615-2.
Lin, Shu, and Daniel J. Costello, Jr. «Error Control Coding: Fundamentals and Applications». Englewood Cliffs, N.J.: Prentice-Hall, 1983. ISBN 0-13-283796-X.
Mackenzie, Dana. «Communication speed nears terminal velocity». New Scientist 187.2507 (9 июля 2005): 38-41. ISSN 0262-4079.
Wicker, Stephen B. Error Control Systems for Digital Communication and Storage. Englewood Cliffs, N.J.: Prentice-Hall, 1995. ISBN 0-13-200809-2.
Wilson, Stephen G. Digital Modulation and Coding, Englewood Cliffs, N.J.: Prentice-Hall, 1996. ISBN 0-13-210071-1.

Ссылки править

Charles Wang, Dean Sklar, and Diana Johnson. Forward Error-Correction Coding (неопр.). The Aerospace Corporation. — Volume 3, Number 1 (Winter 2001/2002). Дата обращения: 24 мая 2009. Архивировано из оригинала 20 февраля 2005 года. (англ.)
Charles Wang, Dean Sklar, and Diana Johnson. How Forward Error-Correcting Codes Work (неопр.). The Aerospace Corporation. Дата обращения: 24 мая 2009. Архивировано из оригинала 25 февраля 2012 года. (англ.)
Morelos-Zaragoza, Robert The Error Correcting Codes (ECC) Page (неопр.) (2004). Дата обращения: 24 мая 2009. Архивировано из оригинала 25 февраля 2012 года. (англ.)

[Thompson-1] Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), The Mathematical Association of America, p. vii, ISBN 0-88385-023-0

[2] Shannon, C.E. (1948), "A Mathematical Theory of Communication", Bell System Technical Journal, p. 418, 27 (3): 379—423, doi:10.1002/j.1538-7305.1948.tb01338.x, hdl:10338.dmlcz/101429, PMID 9230594{{citation}}: Википедия:Обслуживание CS1 (location) (ссылка)

[3] Golay, Marcel J. E. (1949), "Notes on Digital Coding", Proc.I.R.E. (I.E.E.E.), p. 657, 37{{citation}}: Википедия:Обслуживание CS1 (location) (ссылка)

[4] Understanding Digital Television: An Introduction to Dvb Systems With … — Lars-Ingemar Lundström — Google Книги (неопр.). Дата обращения: 19 мая 2020. Архивировано 11 ноября 2021 года.

[5] Ahlswede, R.; Ning Cai; Li, S.-Y.R.; Yeung, R.W., «Network information flow», Information Theory, IEEE Transactions on, vol.46, no.4, pp.1204-1216, Jul 2000

[6] Статьи:
Koetter R., Kschischang F.R. Coding for errors and erasures in random network coding// IEEE International Symposium on Information Theory. Proc.ISIT-07.-2007.- P. 791—795.

Silva D., Kschischang F.R. Using rank-metric codes for error correction in random network coding // IEEE International Symposium on Information Theory. Proc. ISIT-07. — 2007.

Koetter R., Kschischang F.R. Coding for errors and erasures in random network coding // IEEE Transactions on Information Theory. — 2008- V. IT-54, N.8. — P. 3579-3591.

Silva D., Kschischang F.R., Koetter R. A Rank-Metric Approach to Error Control in Random Network Coding // IEEE Transactions on Information Theory.- 2008- V. IT-54, N. 9.- P.3951-3967.

[7] Koetter R., Kschischang F.R. Coding for errors and erasures in random network coding// IEEE International Symposium on Information Theory. Proc.ISIT-07.-2007.- P. 791—795.

[8] Silva D., Kschischang F.R. Using rank-metric codes for error correction in random network coding // IEEE International Symposium on Information Theory. Proc. ISIT-07. — 2007.

[9] Koetter R., Kschischang F.R. Coding for errors and erasures in random network coding // IEEE Transactions on Information Theory. — 2008- V. IT-54, N.8. — P. 3579-3591.

[10] Silva D., Kschischang F.R., Koetter R. A Rank-Metric Approach to Error Control in Random Network Coding // IEEE Transactions on Information Theory.- 2008- V. IT-54, N. 9.- P.3951-3967.

[1]

[2]

[3]

[4]

[5]

[6]