Institute of Information Science - University of Miskolc

User Tools

Site Tools

Trace: • error_detection_and_correction • basic_communication_structures • base64_coding
tanszek:oktatas:techcomm:error_detection_and_correction

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:error_detection_and_correction [2024/10/06 18:33] – [Example] kneheztanszek:oktatas:techcomm:error_detection_and_correction [2024/11/12 07:33] (current) – [How Hamming Codes Work] knehez
Line 1: Line 1:
 +===== Elias-style block protection =====
 +
 +Elias-style block protection uses horizontal and vertical control bits. It should be used if the protected data can be written in matrix form. During the decoding process, the logical values of the equations are examined both individually and combined.
 +
 +**Example**
 +
 +A binary data which is stored in a 3x3 matrix is given: **101011001**
 +
 +Let's write it down in matrix form and attach parity bits, too.
 +
 +|  1  |  0  |  1  |  **0**  |
 +|  0  |  1  |  1  |  **0**  |
 +|  0  |  0  |  1  |  **1**  |
 +|  **1**  |  **1**  |  **1**  |  **1**  |
 +
 +Let's suppose that the first bit was wrong during transmission, then the parity bit in the row and column will show us the bad bit:
 +
 +|  1->0  |  0  |  1  |  **0** -> **1**  |
 +|  0  |  1  |  1  |  **0**  |
 +|  0  |  0  |  1  |  **1**  |
 +|  **1** -> **0**  |  **1**  |  **1**  |  **1** -> **0**  |
 +
 +
 +
 +
 ===== Error Detection and Correction Using Hamming Codes ===== ===== Error Detection and Correction Using Hamming Codes =====
  
Line 7: Line 32:
 $$ n = m + r $$ $$ n = m + r $$
  
-If two code-words are given, for example : **0101110** and **001111110** and the only difference between them is 1 bit, then the 'Hamming distance' of these code-words will be 1. This is an interesting measure for distance because it does not matter which bit in the row is different or whether it belongs to a binary or decimal system. So for example : **45635263** and **45615263** have the Hamming distance of 1 too. It does not matter that 10 different digits could be in the place of the wrong digit.+If two code-words are given, for example : **0101110** and **0111110** and the only difference between them is 1 bit, then the 'Hamming distance' of these code-words will be 1. This is an interesting measure for distance because it does not matter which bit in the row is different or whether it belongs to a binary or decimal system. So for example : **45635263** and **45615263** have the Hamming distance of 1 too. It does not matter that 10 different digits could be in the place of the wrong digit.
  
 The **Hamming-style** correction code supposed to increase the number of parity bits. To correct single bit errors we have to use **k** number of parity bits using this formula: The **Hamming-style** correction code supposed to increase the number of parity bits. To correct single bit errors we have to use **k** number of parity bits using this formula:
Line 31: Line 56:
 For example, in an 11-bit data block, we might have 4 parity bits, making it a 15-bit Hamming code. For example, in an 11-bit data block, we might have 4 parity bits, making it a 15-bit Hamming code.
  
-  * Detecting Errors: After transmission, the parity bits are recalculated and compared with the received parity bits. If there is any mismatch, the system can determine which bit is incorrect by checking the positions covered by the erroneous parity bits. +  * **Detecting Errors**: After transmission, the parity bits are recalculated and compared with the received parity bits. If there is any mismatch, the system can determine which bit is incorrect by checking the positions covered by the erroneous parity bits. 
-  * Correcting Errors: If a single-bit error is detected, the Hamming code identifies which bit is incorrect (from the parity bits' positions) and corrects it by flipping the bit.+  * **Correcting Errors**: If a single-bit error is detected, the Hamming code identifies which bit is incorrect (from the parity bits' positions) and corrects it by flipping the bit.
  
 ==== Example ==== ==== Example ====
Line 38: Line 63:
 In this simple example we encode 4 bits of data into 7 bits by adding 3 parity bits. In this simple example we encode 4 bits of data into 7 bits by adding 3 parity bits.
  
-**Data Bits**: Let’s say we want to transmit the 4-bit data **1011**.+**Data Bits**: Let’s say we want to transmit the 4-bit data **1010**.
  
 **Placement of Parity Bits**: The 7-bit Hamming code places the parity bits in positions that are powers of 2: positions 1, 2, and 4. So, the 7-bit frame will look like this (with p1, p2, p4 being the parity bits): **Placement of Parity Bits**: The 7-bit Hamming code places the parity bits in positions that are powers of 2: positions 1, 2, and 4. So, the 7-bit frame will look like this (with p1, p2, p4 being the parity bits):
 <code>p1 p2 d1 p4 d2 d3 d4</code> <code>p1 p2 d1 p4 d2 d3 d4</code>
-Filling in the data **1011**: +Filling in the data **1010**: 
-<code>p1 p2 1 p4 0 1 1</code>+<code>p1 p2 1 p4 0 1 0</code>
 **Calculating Parity Bits**: We calculate the parity bits such that each one covers a specific set of positions: **Calculating Parity Bits**: We calculate the parity bits such that each one covers a specific set of positions:
   * p1 covers bit positions: 1, 3, 5, 7   * p1 covers bit positions: 1, 3, 5, 7
Line 67: Line 92:
  
 ^1. bit^2. bit^3. bit^4. bit^5. bit^6. bit^7. bit^ ^1. bit^2. bit^3. bit^4. bit^5. bit^6. bit^7. bit^
-|p1|p2|1|p4|0|1|1|+|p1|p2|1|p4|0|1|0| 
 + 
 +**p1**: Covers 1, 0, 0 (positions 1, 3, 5, 7), so p1 = 1 (to make the total even). 
 + 
 +**p2**: Covers 0, 1, 0 (positions 2, 3, 6, 7), so p2 = 1 (to make the total even). 
 + 
 +**p4**: Covers 0, 0, 1, 0 (positions 4, 5, 6, 7), so p4 = 1 (to make the total even). 
 + 
 +Thus, the final transmitted Hamming code is: 
 +<code>1 1 1 1 0 1 0</code> 
 + 
 +Let's suppose that because of an error the 3rd bit goes wrong. In this case **p1** and **p2** will be wrong. Because of the **3rd** bit the first and second parity bit will give us wrong values, but the others will not because they do not calculate with the bit standing at the **3rd** place.
  
-**p1**: Covers 1, 0, 1 (positions 1, 3, 5, 7), so p1 = 0 (to make the total even).+The common values of the first and second parity bits are the following: 1, 2, 3, 5, 6, 7. The defective one has to be among these.
  
-**p2**: Covers 0, 1, 1 (positions 2, 3, 6, 7), so p2 = 0 (already even).+However from 5, 6, 7 are included in the good parity bits -> therefore the wrong parity bit is the **3rd** one.  (note that: 1, 2 cannot be wrong in this case. If 1 was wrong, only the **p1** parity bit would be wrong.)
  
-**p4**: Covers 0, 0, 1, 1 (positions 4, 5, 6, 7), so p4 = 0 (already even) 
tanszek/oktatas/techcomm/error_detection_and_correction.1728239623.txt.gz · Last modified: 2024/10/06 18:33 by knehez