Longitudinal redundancy check
A longitudinal redundancy check (LRC), also known as a horizontal redundancy check, is an error-detection technique in data communications that verifies the integrity of a block of transmitted data by generating and appending a check character based on preset rules applied uniformly to each character in the block.[1] The receiving station recomputes the check on the received data using the same rules and compares it to the received check character; a match confirms successful transmission of the block without detected errors.[2]
In operation, LRC organizes data into a two-dimensional array of rows (representing characters or bytes) and columns (representing bit positions), computing a parity bit for each column across all rows to form the LRC byte, which is then transmitted with the data block.[2] This method, often implemented as an XOR operation on corresponding bits across the block, detects single-bit errors and burst errors up to the block length but fails to identify even-numbered errors in the same bit position (Hamming distance of 2).[2] When combined with a vertical redundancy check (VRC), LRC enables both detection and correction of single-bit errors by isolating the faulty bit at the intersection of mismatched row and column parities.[1]
LRC has been widely applied in legacy telecommunication protocols, industrial control systems like Modbus RTU for serial communication, and early data transmission standards to ensure reliability with minimal overhead.[2] Its simplicity allows efficient computation in resource-constrained environments, though modern systems often prefer cyclic redundancy checks (CRC) for superior error-detection performance against multi-bit and burst errors.[2] Despite limitations in undetected error rates (e.g., 3.125% for 32-bit chunks), LRC remains relevant in specific embedded and payment processing applications where low computational cost is prioritized.[2]
Overview
Definition and Purpose
The Longitudinal Redundancy Check (LRC) is a form of redundancy check that is applied independently to each of a parallel group of bit streams within a data block, typically employing a single parity bit for each stream.[1] This method organizes data into rows and columns, where the check is computed longitudinally across the rows for each bit position, generating a check byte that captures the parity of corresponding bits across the entire block.[3]
The primary purpose of LRC is to detect errors in block-based data transmission, enabling the identification of faults such as single-bit flips or burst errors within the block by appending the check byte to the data stream.[2] In practice, data is divided into fixed-size blocks—for instance, sequences of bytes—and the LRC byte is appended to each block to facilitate verification at the receiver, ensuring overall data integrity without correcting the errors.[1]
LRC operates as a longitudinal parity check along the length of the data block, in contrast to vertical parity checks that apply to individual characters or bytes. As an extension, LRC can be combined with vertical redundancy checks (VRC) to enable not only detection but also correction of single-bit errors.[1] XOR-based variants of LRC are employed in specific communication protocols to compute the check value efficiently.[2]
Historical Development
The Longitudinal redundancy check (LRC) emerged as an extension of basic parity techniques for error detection in data transmission. Developed alongside the vertical redundancy check (VRC), which applies parity to individual characters, LRC addressed the limitations of VRC by computing parity across entire blocks of data, enabling detection of burst errors in parallel bit streams. This combination formed a two-dimensional parity scheme, enhancing reliability in serial and parallel transmission environments.[4]
Formalization of LRC occurred through international standards, with the first edition of ISO 1155 published in 1973, replacing the earlier ISO/R 1155 recommendation of 1969 and specifying its use for detecting errors in information messages via a longitudinal parity block check character in 7-bit coded systems.[5][6] This standard was revised in 1978 to refine procedures for synchronous and asynchronous transmission, emphasizing even parity across bit positions in data blocks starting from control characters like STX or SOH.[7] By standardizing LRC, ISO 1155 facilitated its integration into information processing systems, marking a key step in its adoption for reliable data exchange.
A significant milestone in LRC's adoption came in the mid-1980s with its inclusion in Internet Engineering Task Force (IETF) documents for network protocols. RFC 935 (1985), outlining reliable link layer protocols, described LRC as a character-oriented checksum method involving the exclusive-OR of all characters in a frame to ensure an even number of 1 bits, suitable for asynchronous links but noted as weaker than cyclic redundancy checks (CRC).[8] This positioned LRC within early internetworking efforts, alongside protocols like DDCMP, though it was recommended primarily for low-overhead scenarios.
LRC's evolution saw initial widespread use in both serial transmission for character streams and parallel transmission for block data in storage and communication systems. By the 1990s, however, it was largely supplemented in new designs by more robust methods like CRC, which offered superior burst-error detection with polynomial-based computations, while LRC persisted in legacy block-oriented protocols and simple checksum applications.[8][2]
Mechanism
Computation Process
The computation of the Longitudinal Redundancy Check (LRC) involves organizing the data block into a two-dimensional array, with rows representing individual bytes (or characters) and columns representing bit positions (0 to 7). For each column, a parity bit is calculated across all rows, typically using an even parity or XOR operation, to form the 8-bit LRC byte. This LRC byte is then appended to the data block for transmission. The method assumes fixed-width 8-bit bytes and applies to the entire block, such as headers, payload, and control characters. The resulting LRC ensures that the parity (or XOR) of each bit position across the entire block, including the LRC, is even (or zero for XOR). This provides a simple form of error detection by verifying bit-wise consistency at the receiver.[2]
The step-by-step algorithm proceeds as follows: Initialize an 8-bit LRC value to zero. For each byte b_i (where i = 1 to n, and n is the number of bytes in the block excluding LRC), update the LRC by performing a bitwise XOR operation: LRC = LRC XOR b_i. After processing all bytes, the final LRC value is appended to the block. Equivalently, the LRC can be viewed as the XOR of all data bytes, such that including the LRC yields a total XOR of zero. This operation is performed independently on each bit position, aligning with the column parity in the 2D array representation.[9]
Mathematically, let the data bytes be b_1, b_2, \dots, b_n. The LRC is given by:
\text{LRC} = \bigoplus_{i=1}^n b_i
where \oplus denotes bitwise XOR. Thus, the total XOR including LRC, \bigoplus_{i=1}^n b_i \oplus \text{LRC} = 0. This property enables detection of errors that alter the parity in any bit position.[2]
Verification and Error Detection
At the receiving end, the LRC verification process involves recomputing the LRC value over the received data block, excluding the received LRC byte itself, using the identical algorithm applied by the sender. The recomputed value is then compared to the received LRC byte; if they match, the block is deemed valid and accepted, whereas a mismatch indicates an error, prompting the receiver to discard the block and request retransmission. Alternatively, the XOR of the entire block including the received LRC can be computed; it should equal zero for valid transmission. This step ensures data integrity without correcting the errors, relying instead on higher-layer protocols for recovery.[2]
The LRC exhibits strong error detection capabilities for certain error patterns, reliably detecting all single-bit errors within the block due to its Hamming distance of 2. It also detects all odd-numbered bit errors across the block, as these alter the parity in at least one bit position. However, its effectiveness is limited for even-numbered burst errors exceeding the block size, where such errors may align in ways that preserve the parity across columns, potentially going undetected.[2][4]
A key validation criterion in LRC implementations is that the total XOR (or parity) of all block bytes including the LRC byte equals zero; any deviation from this condition signals an error and triggers retransmission.
Undetected errors in LRC occur with low probability under random noise conditions, where the fraction of undetected two-bit errors is approximately 3.125% for typical chunk sizes, but this probability rises significantly for systematic burst errors compared to more robust polynomial-based methods like CRC, which offer better coverage for structured fault patterns.[2]
Variants
Basic LRC
The basic Longitudinal Redundancy Check (LRC) applies longitudinal parity across all bytes in a data block, generating an 8-bit check byte in which each bit corresponds to the parity of the aligned bit positions from every byte in the block. This check byte is appended to the block for transmission, enabling the receiver to verify the integrity of the entire data unit by recomputing the parities.[10]
In contrast to the Vertical Redundancy Check (VRC), which calculates parity vertically within each individual byte to detect errors in single characters, LRC operates horizontally across the sequence of bytes in the block; the basic form functions independently without requiring VRC integration. This horizontal approach ensures that errors affecting multiple bytes can be identified through changes in the block-wide bit parities.[11]
Fundamentally, basic LRC serves as a block checksum based on parity, detecting errors when the recomputed parity of the received block differs from the transmitted check byte due to bit flips or other alterations.[11] It is particularly suited to 8-bit systems, where longitudinal parity is evaluated separately for each of the eight bit positions spanning the block's bytes.[10] The parity byte can be derived by aggregating the bits in each position, often using even or odd parity conventions to maintain consistency across the system.
Optimal Rectangular Code
The Optimal Rectangular Code (ORC) is an enhanced variant of the Longitudinal Redundancy Check (LRC) that incorporates transverse redundancy checks (TRC) to enable error correction within rectangular data blocks. It structures data as an n by (n-1) array, where n represents the number of tracks (typically 9 for magnetic tape systems), with each row consisting of data bytes followed by an LRC check byte computed as the modulo-2 sum of the preceding bytes to ensure even parity. Orthogonal to this, a dedicated parity track runs vertically across all bytes in each column, providing TRC bits that maintain even parity for every horizontal position, including the LRC check bytes themselves. This dual parity mechanism forms parity tracks along both dimensions of the rectangular block, adding minimal overhead—approximately 25% redundancy for a 9-track configuration—while enabling comprehensive error localization.[12][13]
For error correction, ORC identifies single-bit errors through syndrome calculations derived from the parity mismatches. The LRC syndrome, computed by re-summing the bytes in each row against the stored check byte, pinpoints the erroneous byte by indicating which row fails parity; meanwhile, the TRC syndrome, obtained by checking the vertical parity track against the received data columns, identifies the faulty bit position within that byte by flagging the specific track in error. These two syndromes together form an error locator that precisely indicates the row and column of the single-bit fault, allowing correction via bit inversion at that intersection without affecting other data. An overall parity check across the entire block, including the LRC row and TRC column, verifies the integrity of the parity bits themselves, ensuring even parity for the complete rectangular array. This process corrects any single-bit error per block reliably.[12][13]
ORC was developed for high-density magnetic tape storage and transmission systems, such as IBM's 6250 bits-per-inch 3420 series units using 9-track formats, where it addressed error-prone environments like tape wear or signal degradation. It corrects one error per block but can detect (though not correct) multiple errors by identifying parity failures beyond a single mismatch, alerting systems to potential data corruption for retransmission or further processing. This capability made ORC a practical choice for early reliable data handling in batch-oriented tape drives.[12][13]
Implementation
Pseudocode
The pseudocode for computing a longitudinal redundancy check (LRC) provides a straightforward algorithmic implementation for ensuring data integrity during block transmission. According to the ISO 1155 standard, the LRC is calculated as the modulo-2 sum (equivalent to bitwise XOR) of all bytes in the block, resulting in an 8-bit value appended to the block. This method assumes 8-bit byte operations and can be easily adapted to programming languages such as C or Python for processing byte arrays.
The following pseudocode illustrates the ISO 1155 computation process:
initialize lrc = 0
for each byte b in the block:
lrc = lrc XOR b
append lrc to the block
initialize lrc = 0
for each byte b in the block:
lrc = lrc XOR b
append lrc to the block
An alternative iterative form uses arithmetic summation modulo 256 followed by a two's complement adjustment, commonly employed in protocols like Modbus for ASCII mode. This variant computes the sum of bytes, masks to 8 bits, and then applies the negation to ensure the total sum including the LRC is zero modulo 256.
Pseudocode for this alternative:
initialize lrc = 0
for each byte b in the block:
lrc = (lrc + b) AND 0xFF
lrc = ((lrc XOR 0xFF) + 1) AND 0xFF
append lrc to the block
initialize lrc = 0
for each byte b in the block:
lrc = (lrc + b) AND 0xFF
lrc = ((lrc XOR 0xFF) + 1) AND 0xFF
append lrc to the block
To verify the received block, recompute the LRC on the data bytes excluding the received LRC byte, then check if the XOR of the recomputed LRC and the received LRC equals zero; if so, the block is intact. This verification applies to the XOR-based method and assumes no errors in transmission.
Pseudocode for verification (XOR-based):
recomputed_lrc = 0
for each byte b in the received block excluding the final LRC byte:
recomputed_lrc = recomputed_lrc XOR b
if (recomputed_lrc XOR received_lrc) == 0:
block is valid
else:
error detected
recomputed_lrc = 0
for each byte b in the received block excluding the final LRC byte:
recomputed_lrc = recomputed_lrc XOR b
if (recomputed_lrc XOR received_lrc) == 0:
block is valid
else:
error detected
For the arithmetic variant, verification instead checks if the sum of all bytes including the received LRC equals zero modulo 256.
Use in Protocols
The Longitudinal Redundancy Check (LRC) finds application in several communication protocols, particularly those requiring simple, low-overhead error detection in constrained environments. In the Modbus protocol's ASCII mode, LRC serves as the error-checking mechanism, where it is computed as the two's complement of the sum of all bytes in the message frame (excluding start and end delimiters), appended as a two-character hexadecimal value. This approach enables reliable transmission over serial lines in industrial automation systems, such as programmable logic controllers and supervisory control and data acquisition (SCADA) setups.
In electricity metering systems, IEC 62056-21 employs LRC for verifying the integrity of data blocks exchanged between a hand-held unit and tariff devices via serial interfaces. The LRC is calculated by XORing all characters in the data block (per ISO/IEC 1155:1978), excluding start and end characters, and appended as a single byte to detect transmission errors in modes A, B, or C. This method supports local data readout in utility meters for electricity, gas, and thermal energy, ensuring compatibility in embedded, low-power devices.[14]
For smart card communications, ISO/IEC 7816-3 specifies LRC as the default error detection code (optional, unless CRC is used) in the epilogue field of T=1 protocol blocks, computed as the byte-wise XOR of all bytes from the node address (NAD) through the information field (INF), such that the XOR including the LRC equals 00. It is particularly used in contact-based integrated circuit cards for secure data exchange in applications like identification and payment systems, where computational efficiency is paramount.[15]
The ACCESS.bus protocol, designed for connecting PC peripherals such as keyboards and pointing devices, integrates an XOR-based LRC (termed checksum) in message formats, where the final byte is the XOR of all preceding bytes to yield zero upon verification. This facilitates error-free data transfer in low-speed, multi-drop bus topologies for legacy consumer electronics.[16]
LRC remains prevalent in legacy and low-overhead systems, including embedded devices and serial communications, owing to its computational simplicity and the speed of its typical 8-bit XOR variant, which requires minimal processing resources compared to more robust methods.[2] Although it has been largely phased out in high-speed networks in favor of cyclic redundancy checks (CRC) for superior burst-error detection, LRC persists in ISO standards like IEC 62056-21 and ISO/IEC 7816 to maintain backward compatibility and efficiency in resource-limited scenarios.[2]
Evaluation
Comparison to Other Methods
The Longitudinal Redundancy Check (LRC) serves as a specialized form of block checksum, typically employing XOR or modular addition across bytes in a fixed-length data block to compute a parity byte. This approach makes LRC simpler and computationally faster than general checksum methods, such as the Fletcher or Adler algorithms, which use running sums over arbitrary-length data and can better handle variable packet sizes in protocols like IP. Both detect single-bit errors and some double-bit errors with a Hamming distance (HD) of 2, but general checksums offer improved mixing of data bits to reduce undetected error probabilities in longer or variable streams, achieving HD up to 3 for short lengths before degrading.[2][17]
In contrast to Cyclic Redundancy Checks (CRC), LRC relies on straightforward linear operations like byte-wise XOR, whereas CRC performs polynomial division in GF(2), enabling detection of longer burst errors up to the degree of the polynomial plus one (e.g., CRC-16 detects bursts up to 17 bits). LRC exhibits an HD of 2 and detects bursts up to 8 bits for an 8-bit check, making it less reliable for high-noise environments compared to CRC's higher HD (e.g., 4 for CRC-16) and lower undetected error rates. For example, at 10 KB message length and BER=10^{-6}, CRC-16 has an approximate undetected error probability (Pud) of ~10^{-6}, compared to LRC's undetected error fraction of ~3% for 32-bit chunks (a conditional probability given errors). Notably, LRC is mathematically equivalent to an 8-bit CRC using the primitive polynomial x^8 + 1, but standard CRC polynomials like x^{16} + x^{15} + x^2 + 1 provide superior burst error detection and data independence, favoring CRC in applications such as Ethernet frames or storage media where robustness outweighs minimal added complexity.[2][17]
LRC finds use in legacy block-oriented systems like magnetic tapes for quick parity validation, while general checksums suit lightweight network headers, and CRC dominates in demanding scenarios requiring high integrity, such as avionics or file transfers.[2]
| Method | Mechanism | Error Detection Capabilities | Computation Complexity | Hardware Support |
|---|
| LRC (8-bit) | Byte-wise XOR or sum | HD=2; detects 1-bit errors, 8-bit bursts; ~3% undetected fraction for 32-bit chunks | Simple linear ops; O(n) time | Basic gates; no tables needed |
| Checksum (e.g., Fletcher-32) | Running modular addition | HD=2-3; detects 1-2 bit errors; Pud ~10^{-11} at 10KB (BER=10^{-6}) | Addition with carry handling; O(n) | Adders; software-efficient |
| CRC (e.g., 16-bit) | Polynomial division (GF(2)) | HD=4; detects bursts up to 17 bits; Pud ~10^{-6} at 10KB (BER=10^{-6}) | Shift-XOR; table-accelerated | Shift registers; LUTs common |
Strengths and Limitations
One key strength of the Longitudinal Redundancy Check (LRC) is its low computational overhead, as it relies on simple bitwise XOR or addition operations across data blocks, making it suitable for real-time applications and resource-constrained embedded systems.[2] This simplicity also facilitates easy hardware implementation using basic parity generators, which require minimal circuitry compared to more complex codes.[2] Furthermore, LRC effectively detects single-bit errors and short-burst errors within the block size, as it identifies any odd number of errors in vertical slices of the data matrix.[2]
However, LRC has significant limitations as an error-detection method, primarily its inability to correct errors—it only signals their presence, necessitating retransmission in most cases, though extended forms may offer limited correction.[19] It performs poorly against long burst errors exceeding the block size and is vulnerable to systematic errors, such as an even number of bit flips in each column, which leave the check sum unchanged and go undetected.[20] For random bit errors, the undetected error probability is approximately $2^{-8} for an 8-bit LRC on messages longer than 8 bits, offering lower reliability than Cyclic Redundancy Check (CRC) methods, which achieve around $2^{-16} or better.[2] Consequently, LRC has become outdated for high-speed networks since the 1990s, where more robust codes prevail.[2]
In applications, LRC remains best suited for low-bandwidth, legacy systems such as bisynchronous protocols, but it lacks integration with forward error correction (FEC) techniques, limiting its use in modern error-resilient environments.[21]