Longitudinal redundancy check

Last updated

In telecommunication, a longitudinal redundancy check (LRC), or horizontal redundancy check, is a form of redundancy check that is applied independently to each of a parallel group of bit streams. The data must be divided into transmission blocks, to which the additional check data is added.

Contents

The term usually applies to a single parity bit per bit stream, calculated independently of all the other bit streams (BIP-8), [1] [2] although it could also be used to refer to a larger Hamming code. [ citation needed ]

This "extra" LRC word at the end of a block of data is very similar to checksum and cyclic redundancy check (CRC).

Optimal rectangular code

While simple longitudinal parity can only detect errors, it can be combined with additional error-control coding, such as a transverse redundancy check (TRC), to correct errors. The transverse redundancy check is stored on a dedicated "parity track".

Whenever any single-bit error occurs in a transmission block of data, such two-dimensional parity checking, or "two-coordinate parity checking", [3] enables the receiver to use the TRC to detect which byte the error occurred in, and the LRC to detect exactly which track the error occurred in, to discover exactly which bit is in error, and then correct that bit by flipping it. [4] [5] [6]

Pseudocode

International standard ISO 1155 [7] states that a longitudinal redundancy check for a sequence of bytes may be computed in software by the following algorithm:

lrc := 0 for each byte b in the buffer dolrc := (lrc + b) and 0xFF lrc := (((lrc XOR 0xFF) + 1) and 0xFF)

which can be expressed as "the 8-bit two's-complement value of the sum of all bytes modulo 28" (x AND 0xFF is equivalent to x MOD 28).

Other Forms

Many protocols use an XOR-based longitudinal redundancy check byte (often called block check character or BCC), including the serial line internet protocol (SLIP), [8] the IEC 62056-21 standard for electrical-meter reading, smart cards as defined in ISO/IEC 7816, and the ACCESS.bus protocol.

An 8-bit LRC such as this is equivalent to a cyclic redundancy check using the polynomial x8 + 1, but the independence of the bit streams is less clear when looked at in that way.

Related Research Articles

Checksum A small-size datum computed from digital data for detecting transmission errors

A checksum is a small-sized datum derived from a block of digital data for the purpose of detecting errors that may have been introduced during its transmission or storage. It is usually applied to an installation file after it is received from the download server. By themselves, checksums are often used to verify data integrity but are not relied upon to verify data authenticity.

In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.

The Transmission Control Protocol (TCP) is one of the main protocols of the Internet protocol suite. It originated in the initial network implementation in which it complemented the Internet Protocol (IP). Therefore, the entire suite is commonly referred to as TCP/IP. TCP provides reliable, ordered, and error-checked delivery of a stream of octets (bytes) between applications running on hosts communicating via an IP network. Major internet applications such as the World Wide Web, email, remote administration, and file transfer rely on TCP, which is part of the Transport Layer of the TCP/IP suite. SSL/TLS often runs on top of TCP.

A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents. On retrieval, the calculation is repeated and, in the event the check values do not match, corrective action can be taken against data corruption. CRCs can be used for error correction.

A frame is a digital data transmission unit in computer networking and telecommunication. In packet switched systems, a frame is a simple container for a single network packet. In other telecommunications systems, a frame is a repeating structure supporting time-division multiplexing.

Hamming code family of linear error-correcting codes

In telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect up to two-bit errors or correct one-bit errors without detection of uncorrected errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance of three. Richard W. Hamming invented Hamming codes in 1950 as a way of automatically correcting errors introduced by punched card readers. In his original paper, Hamming elaborated his general idea, but specifically focused on the Hamming(7,4) code which adds three parity bits to four bits of data.

In telecommunications, a transverse redundancy check (TRC) or vertical redundancy check is a redundancy check for synchronized parallel bits applied once per bit time, across the bit streams. This requires additional parallel channels for the check bit or bits.

In computer networking, the transport layer is a conceptual division of methods in the layered architecture of protocols in the network stack in the Internet protocol suite and the OSI model. The protocols of this layer provide host-to-host communication services for applications. It provides services such as connection-oriented communication, reliability, flow control, and multiplexing.

The data link layer, or layer 2, is the second layer of the seven-layer OSI model of computer networking. This layer is the protocol layer that transfers data between adjacent network nodes in a wide area network (WAN) or between nodes on the same local area network (LAN) segment. The data link layer provides the functional and procedural means to transfer data between network entities and might provide the means to detect and possibly correct errors that may occur in the physical layer.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

A parity bit, or check bit, is a bit added to a string of binary code to ensure that the total number of 1-bits in the string is even or odd. Parity bits are used as the simplest form of error detecting code.

ISO/IEC 2022Information technology—Character code structure and extension techniques, is an ISO standard specifying

Modbus is a serial communications protocol originally published by Modicon in 1979 for use with its programmable logic controllers (PLCs). Modbus has become a de facto standard communication protocol and is now a commonly available means of connecting industrial electronic devices. Modbus is popular in industrial environments because it is openly published and royalty-free. It was developed for industrial applications, is relatively easy to deploy and maintain compared to other standards, and places few restrictions other than size on the format of the data to be transmitted.

The Fletcher checksum is an algorithm for computing a position-dependent checksum devised by John G. Fletcher (1934–2012) at Lawrence Livermore Labs in the late 1970s. The objective of the Fletcher checksum was to provide error-detection properties approaching those of a cyclic redundancy check but with the lower computational effort associated with summation techniques.

The Open Systems Interconnection protocols are a family of information exchange standards developed jointly by the ISO and the ITU-T. The standardization process began in 1977.

A frame check sequence (FCS) refers to an error-detecting code added to a frame in a communications protocol. Frames are used to send payload data from a source to a destination.

CRC-based framing is a kind of frame synchronization used in Asynchronous Transfer Mode (ATM) and other similar protocols.

ISO/IEC 7813 is an international standard codified by the International Organization for Standardization and International Electrotechnical Commission that defines properties of financial transaction cards, such as ATM or credit cards.

Binary Synchronous Communication is an IBM character-oriented, half-duplex link protocol, announced in 1967 after the introduction of System/360. It replaced the synchronous transmit-receive (STR) protocol used with second generation computers. The intent was that common link management rules could be used with three different character encodings for messages. Six-bit Transcode looked backwards to older systems; USASCII with 128 characters and EBCDIC with 256 characters looked forward. Transcode disappeared very quickly but the EBCDIC and USASCII dialects of Bisync continued in use.

When writing firmware for an embedded system, immunity-aware programming refers to programming techniques which improve the tolerance of transient errors in the program counter or other modules of a program that would otherwise lead to failure. Transient errors are typically caused by single event upsets, insufficient power, or by strong electromagnetic signals transmitted by some other "source" device.

References

  1. RFC   935: "Reliable link layer protocols".
  2. "Errors, Error Detection, and Error Control: Data Communications and ComputerNetworks: A Business User's Approach".
  3. .
  4. Gary H. Kemmetmueller. "RAM error correction using two dimensional parity checking".
  5. Oosterbaan. "Longitudinal parity".
  6. "Errors, Error Detection, and Error Control".
  7. ISO 1155:1978 Information processing -- Use of longitudinal parity to detect errors in information messages.
  8. RFC   914. "A Thinwire Protocol for connecting personal computers to the INTERNET". Appendix D: "Serial Line Interface Protocol (SLIP)".