Institute of Information Science - University of Miskolc

User Tools

Site Tools

Trace:
tanszek:oktatas:techcomm:reed-solomon_codes

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
tanszek:oktatas:techcomm:reed-solomon_codes [2024/10/06 19:32] – [Setup] kneheztanszek:oktatas:techcomm:reed-solomon_codes [2024/10/06 19:43] (current) – [Step 1: Data Symbols] knehez
Line 1: Line 1:
 +~~NOTOC~~
 ==== Reed-Solomon codes ==== ==== Reed-Solomon codes ====
 +
 +**Reed-Solomon (RS) codes** are a type of **error-correcting code** used to detect and correct data transmission or storage errors. They are particularly effective at correcting burst errors, where multiple consecutive bits are corrupted. Reed-Solomon codes are widely used in applications like **CDs, DVDs, QR codes, satellite communications**, and **data storage systems**.
 +
 +==== Key Concepts ====
 +
 +=== 1. Symbols Instead of Bits ===
 +Unlike simpler error-correcting codes (such as Hamming codes, which operate on individual bits), Reed-Solomon codes operate on **symbols**. A symbol is a block of bits (e.g., 8 bits) that represents a larger unit of data.
 +
 +For example, in an 8-bit RS code, each symbol is an 8-bit value, allowing the code to work on groups of 8 bits (1 byte) at a time. RS codes can handle burst errors, meaning they can correct errors that affect multiple consecutive bits in a single symbol.
 +
 +=== 2. Block-Based Code ===
 +Reed-Solomon codes are **block codes**, meaning they work by dividing data into fixed-size blocks and encoding each block independently.
 +
 +  * **Message Length**: The number of data symbols in a block.
 +  * **Codeword Length**: The total number of symbols (including parity) in a block after encoding.
 +  
 +For example, in a typical RS code, you might have a message length of `k` data symbols and a codeword length of `n` total symbols, where `n > k`. The difference (`n - k`) represents the number of **redundant (parity)** symbols added for error correction.
 +
 +=== 3. Error Correction Capability ===
 +Reed-Solomon codes can detect and correct multiple symbol errors. Specifically, an RS code can correct up to `(n - k) / 2` symbols of errors in a block. 
 +
 +  * Error correction capability: The number of correctable symbols depends on how many parity symbols are added. More parity symbols increase the error-correcting strength but also increase the overhead.
 +
 We'll use a simplified version with small numbers to make the process easier to understand. Typically, Reed-Solomon codes use larger fields (like 255 symbols for CDs), but in this example, we'll use a smaller field size. We'll use a simplified version with small numbers to make the process easier to understand. Typically, Reed-Solomon codes use larger fields (like 255 symbols for CDs), but in this example, we'll use a smaller field size.
  
Line 5: Line 29:
  
 Let's use the Reed-Solomon code **RS(7, 3)**, which means: Let's use the Reed-Solomon code **RS(7, 3)**, which means:
-- **n = 7**: The total number of symbols in the codeword. + 
-- **k = 3**: The number of original data symbols. +  - **n = 7**: The total number of symbols in the codeword. 
-- **n - k = 4**: The number of parity symbols added for error correction.+  - **k = 3**: The number of original data symbols. 
 +  - **n - k = 4**: The number of parity symbols added for error correction.
  
 The codeword will be composed of 7 symbols: 3 data symbols and 4 parity symbols. We'll assume we're working in **GF(8)** (Galois Field of 8 elements), with the following primitive polynomial:  The codeword will be composed of 7 symbols: 3 data symbols and 4 parity symbols. We'll assume we're working in **GF(8)** (Galois Field of 8 elements), with the following primitive polynomial: 
Line 27: Line 52:
 Let’s assume we want to encode the following **3 data symbols**: Let’s assume we want to encode the following **3 data symbols**:
 \[ \[
-\text{Data} = \{ 6, 4, 3 \}+\text{data} = \{ 6, 4, 3 \}
 \] \]
  
Line 84: Line 109:
 ====Step 7: Error Introduction==== ====Step 7: Error Introduction====
  
-Assume there is a transmission error, and the received codeword has errors in two symbols:+Assume there is a transmission error, and the received codeword has errors in one symbol:
  
 \[ \[
Line 93: Line 118:
 ====Step 8: Error Detection and Correction==== ====Step 8: Error Detection and Correction====
  
-Using the Reed-Solomon decoding algorithm (which involves using syndromes and solving the error locator polynomial), the receiver can detect that an error occurred and identify the erroneous symbol(s). Based on the parity and the syndromes, it would determine that the 6th symbol is incorrect and correct it back to the original value (4).+Using the Reed-Solomon decoding algorithm (which involves solving the error locator polynomial), the receiver can detect that an error occurred and identify the erroneous symbol(s). Based on the parity and the syndromes, it would determine that the 6th symbol is incorrect and correct it back to the original value (4).
  
 Thus, the corrected codeword would be: Thus, the corrected codeword would be:
Line 103: Line 128:
 ====Summary of Steps==== ====Summary of Steps====
  
-1. **Encode**: Multiply the data polynomial by \(x^{n-k}\) and divide by the generator polynomial to find the parity. +  * 1. **Encode**: Multiply the data polynomial by \(x^{n-k}\) and divide by the generator polynomial to find the parity. 
-2. **Transmit**: Send the data and parity as a codeword. +  * 2. **Transmit**: Send the data and parity as a codeword. 
-3. **Detect and Correct**: Upon receiving the (possibly corrupted) codeword, calculate syndromes and use the Reed-Solomon algorithm to correct errors.+  * 3. **Detect and Correct**: Upon receiving the (possibly corrupted) codeword, calculate syndromes and use the Reed-Solomon algorithm to correct errors.
  
 ====Applications==== ====Applications====
tanszek/oktatas/techcomm/reed-solomon_codes.1728243142.txt.gz · Last modified: 2024/10/06 19:32 by knehez