Продольный контроль по избыточности
Продольный контроль по избыточности (LRC) или горизонтальный контроль избыточности — это вид контроля ошибок, применяемый независимо к каждому из параллельных потоков битов. Данные должны быть разделены на блоки для передачи, к которым добавляются дополнительные проверочные данные.
Термин обычно относится к одному биту чётности для каждого потока битов, вычисляемому независимо от всех других потоков битов (BIP-8)[1][2].
Это «дополнительное» слово LRC в конце блока данных очень похоже на контрольную сумму и циклическую проверку избыточности (CRC).
Оптимальный прямоугольный код
Простая продольная чётность может только обнаружить ошибки, но в сочетании с дополнительным кодированием для контроля ошибок, таким как поперечный контроль по избыточности (transverse redundancy check, TRC), позволяет их исправлять. Поперечная проверка избыточности хранится на специальной «дорожке чётности».
Когда в блоке передаваемых данных возникает ошибка в одном бите, такая двумерная проверка чётности, или «двухкоординатная проверка чётности»[3], позволяет приёмнику использовать TRC для определения байта, в котором ошибка произошла, и LRC для определения дорожки, содержащей ошибку, что даёт точное положение ошибочного бита и позволяет исправить его путём инвертирования[4][5][6].
Псевдокод
Международный стандарт ISO 1155[7] утверждает, что продольный контроль по избыточности для последовательности байт может быть вычислен программно следующим алгоритмом:
lrc := 0
for each byte b in the buffer do
lrc := (lrc + b) and 0xFF
lrc := (((lrc XOR 0xFF) + 1) and 0xFF)
который может быть выражен как «8-битное значение в дополнительном коде суммы всех байтов по модулю 28» (x AND 0xFF эквивалентно x MOD 28).
Другие формы
Многие протоколы используют байт продольной избыточности на основе операции XOR (часто называемый контрольным символом блока или BCC), включая межсетевой протокол для последовательных интерфейсов[a] (SLIP, не путать с более поздним и хорошо известным межсетевым протоколом для последовательного канала)[8], стандарт IEC 62056-21 для считывания показаний электросчётчиков, смарт-карты, определённые в ISO/IEC 7816 и протокол ACCESS.bus.
8-битный LRC, подобный этому, эквивалентен циклическому избыточному коду с использованием многочлена x8 + 1, однако независимость потоков битов менее очевидна при таком рассмотрении.
Примечания
- ↑ Serial Line Interface Protocol (протокол для последовательных интерфейсов). SLIP - это протокол, похожий на PPP в том, что он используется для соединения двух машин через последовательный интерфейс.
- ↑ RFC 935: "Reliable link layer protocols".
- ↑ "Errors, Error Detection, and Error Control: Data Communications and ComputerNetworks: A Business User's Approach".
- ↑ Chapter1. Дата обращения: 20 августа 2012. Архивировано из оригинала 13 июня 2013 года.
- ↑ Gary H. Kemmetmueller. "RAM error correction using two dimensional parity checking".
- ↑ Oosterbaan. "Longitudinal parity".
- ↑ "Errors, Error Detection, and Error Control".
- ↑ ISO 1155:1978 Information processing -- Use of longitudinal parity to detect errors in information messages.
- ↑ RFC 914. "A Thinwire Protocol for connecting personal computers to the INTERNET". Appendix D: "Serial Line Interface Protocol (SLIP)".