Hacker Perspective:: Data Notes: Introduction to Error Detection & Error Correction

Introduction to VPC, LPC, CRC, ECC

• You need to know about this ancient stuff because it is the basis for more advanced modern technologies.
  • Recommendation: click https://www.bookfinder.com then purchase a copy of Technical Aspects of Data Communication by John McNamara (Digital Equipment Corporation)
• The history of error detection goes back to the earliest days of the TWX network (which ran in parallel with the analog telephone network) to enabled teletypes to communicate between banks, insurance companies, and governments. Recording was usually done with paper tape. To keep costs down, the tape was prepared ahead of time. When complete, the data was sent via a tape reader which behaved as a fast keyboarder.
• As data technology migrated from electromechanical modems (tuned with a wrench) to electronic modems, more elaborate error detection enabled single-bit (and limited multi-bit) error correction.
• In the early days of modems, data was only thought of as being sent character-by-character (5-bit for the Baudot code employed by teletypes; 7-bit for plain ASCII which was popular in the very first CRT terminals, 8-bit for ISO-8859-1 which was popular in Unix terminals) followed by a single parity bit for each character.
• Note that HTTPS over a dialup modem may send 8-bit information serially but this is usually done in blocks followed by one or two Block Check Characters (similar to CRC) but not individual parity bits.
• At this same time we see a lot of error detection and error correction added to data storage systems like magnetic tape technology which was a precursor to magnetic disk technology and optical disc technology
• parity bit
  • first seen with paper tape; mechanical modems; then electronic modems
  • with even parity, all of the data bits including the parity bit must be even (0)
  • with odd parity, all of the data bits including the parity bit must be odd (1)
• VPC
  • Vertical Parity Check
  • also known as VRC (Vertical Redundancy Check)
  • in a data block (think of a 9-track magnetic tape) the first 8-bits represent data while the ninth bit records the parity
  • the 8-bits are supplied by the computer system; the parity bit is generated/tested by the tape system
  • WARNING:  VPC will only detect single-bit errors when used alone. Two errors escape notice.
• LPC
  • Longitudinal Parity Check
  • also known as LRC (Longitudinal Redundancy Check) via the LRCC (Longitudinal Redundancy Check Character)
  • in a data block (think of a 9-track magnetic tape) a parity bit is reserved for each horizontal data bit (including the parity channel)
  • when LPC is coupled with VPC:
    • single-bit errors are now correctable
    • multi-bit errors (including a dead track) are now correctable
• CRC
  • Cyclic Redundancy Check
  • a mathematical method of encoding the data which may allow the correction of multi-bit errors
  • the tape system might not contain enough processing power to recover all bad data but the connected computer system may be able to do it.
• ECC
  • Error Correcting Code
  • Quote from: PDP-11_Processor_Handbook_1981.pdf

    ECC (error correcting code) is a technique for checking the contents of memory to detect errors and correct them before sending them to the processor. The process of checking is accomplished by combining the bits in a number of unique ways so that parity, or syndrome, bits are generated for each unique combination and stored along with the data bits in the same word as the data. The memory word length is extended to store these unique bits. When memory is read, the data word is checked against the syndrome bits stored with the word. If they match, the word is sent on to the processor. If they do not match, an error exists and the mismatch of the syndrome bits determines which data bit is in error. The bit in error is then corrected and sent on to the processor. The error correcting code which is employed in MOS memory will detect and correct single bit errors in a word, and detect double bit errors in a word. Where a double bit error is detected, the processor is notified, as happens with a parity error.

  • The first time I was exposed to ECC memory which appeared to be synonymous with magic was on the PDP-11/44 manufactured by DEC (Digital Equipment Corporation)
  • This ECC scheme involved laying out the memory module in 39-bit rows (32-bits of data; 7-bits of syndrome)
  • https://bitsavers.org/pdf/dec/pdp11/1144/
  • https://en.wikipedia.org/wiki/Decoding_methods#Syndrome_decoding
  • ECC Memory Explained: https://www.youtube.com/watch?v=pPeCNrNTr3k

Example 1 (VPC)

==========================================================================
title: page-01-vpc.txt
ref  :
1) https://bitsavers.org/pdf/hp/tape/7970/
2) https://bitsavers.org/pdf/dec/magtape/tu16/
notes:
1) this info applies to 9-track tape systems like the HP-7970e
2) this example shows a hypothetical 16-byte block without LPC/BCC/CRC
   (an end-of-block gap exists after the last data byte)
3) dp (data parity) is also called VPC (vertical parity check)
4) during a write operation, data bits are supplied from the computer. The
   tape system uses these data bits to compute the VPC bit which is
   recorded with the rest
5) during a read operation, data bits are supplied by the tape medium. The
   tape system uses these bits to compute the parity bit which is compared
   with the VPC bit (match=good data; mismatch=error)
6) NRZI encoding employed odd parity so that something was written to tape
   even when all data bits were zero
7) this example demonstrates odd parity (all vertical data bits + VPC = 1)
   so we need an odd number of ones in each vertical column
8) ASCII bit 'f3' = X (was written as '0' but is being read as '1')
   expected parity: 1
   VPC data       : 0 (so column f is in error but the row is unknown)
9) WARNING: VPC will only detect single-bit errors. Two errors will escape
   notice.
==========================================================================
+-------------------------------------------- IBM / HP track number
| +------------------------------------------ ANSI track number
| | ++++------------------------------------- ASCII bit designations
| | |||| 0 1 2 3 4 5 6 7 8 9 a b c d e f ---- per-block character count
| | |||| | | | | | | | | | | | | | | | | +--- end-of-block gap
0 7 d0/Z 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 .    binary data 0
7 2 d1   0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 .    binary data 1
6 8 d2   0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 .    binary data 2
5 1 d3   0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 X .    binary data 3
4 9 d4   0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 .    binary data 4
3 3 d5   0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 .    binary data 5
2 5 d6   0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 .    binary data 6
1 6 d7   1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 .    binary data 7
P 4 dp/P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .    parity data (VPC)
==========================================================================

Example 2 (LPC / LRC / LRCC)

==========================================================================
title: page-02-lpc.txt
ref  :
1) https://bitsavers.org/pdf/hp/tape/7970/
2) https://bitsavers.org/pdf/dec/magtape/tu16/
notes:
1) this info applies to 9-track tape systems like the HP-7970e
2) this example shows a hypothetical 16-byte block with trailing LPC
   (an end-of-data block gap separates data from LPC)
3) see 'page-01-vpc.txt' for info about VPC
4) LPC (Longitudinal Parity Check) is also known as LRC (R=redundancy)
5) this example shows odd parity (all horizontal data bits + LPC = 1)
   so we need an odd number of ones on each horizontal row
6) ASCII bit 'f3' = X (was written as '0' but is being read as '1')
   expected VPC parity: 1
   VPC data           : 0 (so column f is in error)
   expected LPC parity: 0
   LPC data           : 1 (so row    3 is in error)
6) Now that we know that bit f3 is in error we can correct it
7) Also notice that the very last bit is protecting both the VPC
   row and LPC column (error checking the parity scheme)
==========================================================================
+---------------------------------------------- IBM / HP track number
| +-------------------------------------------- ANSI track number
| | ++++--------------------------------------- ASCII bit designations
| | |||| 0 1 2 3 4 5 6 7 8 9 a b c d e f ------ per-block character count
| | |||| | | | | | | | | | | | | | | | | +----- end-of-block gap 
| | |||| | | | | | | | | | | | | | | | | | +--- LPC (LRC)
0 7 d0/Z 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 . 1    binary data 0
7 2 d1   0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 . 1    binary data 1
6 8 d2   0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 . 1    binary data 2
5 1 d3   0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 X . 1    binary data 3
4 9 d4   0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 . 1    binary data 4
3 3 d5   0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 . 1    binary data 5
2 5 d6   0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 . 1    binary data 6
1 6 d7   1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 . 1    binary data 7
P 4 dp/P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . 1    parity data (VPC)
==========================================================================

Example 3 (CRC)

==========================================================================
title: page-03-crc.txt
ref  :
1) https://bitsavers.org/pdf/hp/tape/7970/
2) https://bitsavers.org/pdf/dec/magtape/tu16/
3) https://en.wikipedia.org/wiki/Cyclic_redundancy_check
notes:
1) this info applies to 9-track tape systems like the HP-7970e
2) this example shows a hypothetical 16-byte block with LPC + CRC
2a shown this way for clarity but the CRC is always written before LPC
2b LPC only protects data bits but not CRC bits
3) see 'page-01-vpc.txt' for info about VPC
4) see 'page-02-lpc.txt' for info about LPC
5) CRC (cyclic redundancy check)
==========================================================================
+------------------------------------------------- IBM / HP track number
| +----------------------------------------------- ANSI track number
| | ++++------------------------------------------ ASCII bit designations
| | |||| 0 1 2 3 4 5 6 7 8 9 a b c d e f --------- per-block character count
| | |||| | | | | | | | | | | | | | | | | +-------- end-of-block gap
| | |||| | | | | | | | | | | | | | | | | | +------ LPC (LRC)
| | |||| | | | | | | | | | | | | | | | | | | +---- gap
| | |||| | | | | | | | | | | | | | | | | | | | +-- CRC
0 7 d0/Z 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 . 1 . c   binary data 0
7 2 d1   0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 . 1 . c   binary data 1
6 8 d2   0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 . 1 . c   binary data 2
5 1 d3   0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 X . 1 . c   binary data 3
4 9 d4   0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 . 1 . c   binary data 4
3 3 d5   0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 . 1 . c   binary data 5
2 5 d6   0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 . 1 . c   binary data 6
1 6 d7   1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 . 1 . c   binary data 7
P 4 dp/P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . 1 . ?   parity data (VPC)
==========================================================================

Links

---

Back to Home
Neil Rieck
Waterloo, Ontario, Canada.