Scribd
Upload
66 views12 pages

Pres 3

The document discusses error-correcting codes, which add redundant bits to transmitted data to detect and correct errors. It provides examples of Hamming codes and convolutional codes. Hamming codes add parity bits to blocks of data bits to correct single-bit errors. Convolutional codes use a sliding window to encode arbitrary lengths of data and are often decoded with the Viterbi algorithm. Error-correcting codes are widely used in communication technologies like CDMA, GSM, Wi-Fi, and hard disk drives to improve reliability. The document also discusses theoretical limits on error correction from Shannon's theorem.

Uploaded by

Ahmed Elwazeer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
66 views12 pages

Pres 3

The document discusses error-correcting codes, which add redundant bits to transmitted data to detect and correct errors. It provides examples of Hamming codes and convolutional codes. Hamming codes add parity bits to blocks of data bits to correct single-bit errors. Convolutional codes use a sliding window to encode arbitrary lengths of data and are often decoded with the Viterbi algorithm. Error-correcting codes are widely used in communication technologies like CDMA, GSM, Wi-Fi, and hard disk drives to improve reliability. The document also discusses theoretical limits on error correction from Shannon's theorem.

Uploaded by

Ahmed Elwazeer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Amr Kabardy

Kabardy@uw.edu
 What are Error-Correcting Codes?
 How do they works?
 Example: Hamming Codes (7,4)
 Types of Error-Correcting Codes
 Applications
 Basic idea: add redundant bits
 Code Rate: Proportion of data-stream that is useful
 Denoted as Code(n, k), n > k, generates n bits for every k bits
 Code Rate = k / n

 Error Detection Vs Error Correction


 How much errors can be corrected?
 Shannon Limit 1948:
 The theoretical maximum information transfer rate of the channel
 Shannon theorem: ”Given a noisy channel with channel capacity C and information transmitted at
a rate R, then if R < C there exist codes that allow the probability of error at the receiver to be
made arbitrarily small”
Triplet
Interpreted as
received
000 0 (error free)
001 0
010 0
100 0
111 1 (error free)
110 1
101 1
011 1
 In general, to correct m bits, each
valid symbol has to be surrounded
by a sphere of radius m+1 of invalid
codes.
 Introduced by Richard Hamming in
1950, then was frustrated with the
error-prone punched card reader
 For every 4 bits of data: d1, d2, d3, d4
 Add 3 parity bits: p1, p2, p3
 Transmit: p1 p2 d1 p3 d2 d3 d4
 Convolutional Codes:
 Sliding window on bit streams of arbitrary length
 Most often decoded with the Viterbi algorithm

 Block Codes:
 Work on fixed-size blocks of bits
 Generally decoded in polynomial time to their block length
 E.g. Reed-Solomon Code, Golay, BCH, Multidimensional parity, and Hamming codes.

 Turbo Codes:
 Combines two or more relatively simple convolutional codes and an interleaver to
produce a block code
 Convolutional codes used in:
 both CDMA and GSM digital cellular
 dial-up modems
 Satellite and deep-space communications
 802.11wireless LANs

 Reed-Solomon coding has widespread use on the Compact disc, the DVD, and
in hard disk drives
 Hamming ECC is commonly used to correct single level cell NAND flash memory
errors
 LDPC codes are now used in many recent high-speed communication standards:
 DVB-S2 (Digital video broadcasting)
 WiMAX (IEEE 802.16e standard for microwave communications)
 High-Speed Wireless LAN (IEEE 802.11n)
 10GBase-T Ethernet (802.3an)
 G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial
cable).
 Turbo coding CDMA2000 1x and EV-DO
 Digital cellular technology developed by Qualcomm and sold by Verizon Wireless, Sprint,
and other carriers.
 https://en.wikipedia.org/wiki/Noisy-channel_coding_theorem
 https://en.wikipedia.org/wiki/Error_detection_and_correction#Error-
correcting_code
 https://en.wikipedia.org/wiki/Forward_error_correction
 https://en.wikipedia.org/wiki/Code_rate
 http://www.i-programmer.info/babbages-bag/214-error-correcting-
codes.html?start=1
 https://en.wikipedia.org/wiki/Hamming(7,4)
 How do error correction codes work? (Hamming coding)
https://www.youtube.com/watch?v=cBBTWcHkVVY
 https://en.wikipedia.org/wiki/Viterbi_algorithm
 https://en.wikipedia.org/wiki/Convolutional_code
 https://en.wikipedia.org/wiki/Viterbi_decoder
 https://en.wikipedia.org/wiki/Hard_disk_drive
 https://en.wikipedia.org/wiki/Linear_code
Questions?

You might also like