Differences

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

--- tanszek:oktatas:techcomm:error_detection_and_correction [2024/10/06 18:45] – [Example] knehez
+++ tanszek:oktatas:techcomm:error_detection_and_correction [2026/10/19 17:33] (current) – [Example 2.] 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 =====
@@ Line 7: / Line 32: @@
 $$ 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 \(r\) number of parity bits using this formula:
-$$ n + 1 \le 2^k $$
+$$ 2^r \ge m + r + 1 $$
-According to this formula the necessary number of parity bits which are needed to correct single bit errors are stated in the following table (for different word lengths):
+According to this formula the necessary number of parity bits which are needed to correct single bit errors are stated in the following table:
-^ word length ^ number of parity bits ^ whole bit length ^ % of added bits ^
+^ Data bits (\(m\)) ^ number of parity bits (\(r\)) ^ whole bit length (\(n = m + r\)) ^ % of added bits ^
-| 4 | 3 | 7 | 66 |
+| 4 | 3 | 7 | 75 |
 | 8 | 4 | 12 | 50 |
 | 16 | 5 | 21 | 31 |
@@ Line 25: / Line 50: @@
 |512| 10 | 522 | 2 |
-==== How Hamming Codes Work ====
+==== How Hamming Codes Work? ====
 Hamming codes introduce additional bits, called parity bits, into the data. These parity bits are strategically placed within the data to allow the detection of errors. The positions of the parity bits are powers of two (e.g., positions 1, 2, 4, 8, etc.).
@@ 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.
-  * 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 1. ====
 In this simple example we encode 4 bits of data into 7 bits by adding 3 parity bits.
@@ Line 49: / Line 74: @@
   * p4 covers bit positions: 4, 5, 6, 7
-Parity bit **p1** covers all positions where the least significant bit of the position number is **1**. Positions covered: 1, 3, 5, 7 (since 001, 011, 101, and 111 in binary all have a 1 in the least significant bit).
+Parity bit **p1** covers all positions where the **least significant** bit of the position number is **1**. Positions covered: 1, 3, 5, 7 (since 001, 011, 101, and 111 in binary all have a 1 in the least significant bit).
-Parity bit **p2** covers all positions where the second least significant bit is 1. Positions covered: 2, 3, 6, 7 (since 010, 011, 110, and 111 in binary all have a 1 in the second bit).
+Parity bit **p2** covers all positions where the **second least significant** bit is 1. Positions covered: 2, 3, 6, 7 (since 010, 011, 110, and 111 in binary all have a 1 in the second bit).
-Parity bit **p4** covers all positions where the third least significant bit is 1.
+Parity bit **p4** covers all positions where the **third least significant** bit is 1.
 Positions covered: 4, 5, 6, 7 (since 100, 101, 110, and 111 in binary all have a 1 in the third bit).
 In general we can build a table to help to determine covers positions:
-|1. bit|1|3|5|7|9|11|13|15|17|19|21|
+|1. bit (p1)|1|3|5|7|9|11|13|15|17|19|21|
-|2. bit|2|3|6|7|10|11|14|15|18|19| |
+|2. bit (p2)|2|3|6|7|10|11|14|15|18|19| |
-|4. bit|4|5|6|7|12|13|14|15|20|21| |
+|4. bit (p4)|4|5|6|7|12|13|14|15|20|21| |
-|8. bit|8|9|10|11|12|13|14|15| | | |
+|8. bit (p8)|8|9|10|11|12|13|14|15| | | |
-|16. bit|16|17|18|19|20|21| | | | | |
+|16. bit (p16)|16|17|18|19|20|21| | | | | |
 Now calculate the values of parity bits:
@@ Line 71: / Line 96: @@
 **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).
+**p2**: Covers 1, 1, 0 (positions 2, 3, 6, 7), so p2 = 0 (to make the total even).
-**p4**: Covers 0, 0, 1, 0 (positions 4, 5, 6, 7), so p4 = 1 (to make the total even).
+**p4**: Covers 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>
+<code>1 0 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.
+Suppose the 3rd bit is wrong due to an error. In this case, **p1** and **p2** will be wrong. Because of the **3rd** bit the first and second parity bits will give us wrong values, but the others will not because they do not calculate with the bit standing at the **3rd** place.
 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.
-However from 5, 6, 7 are included in the good parity bits -> therefore the wrong parity bit is the **3rd**.  (1, 2 cannot be wrong in this case. If 1 is wrong, only the p1 parity bit would be wrong.)
+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.)
+==== Example 2. ====
+Assume that we try to transmit 16 bits: ''1001011101011011''
+The following table show the placement of the __parity bits__ and the __data bits__:
+| 1| 2|3| 4|5|6|7| 8|9|10|11|12|13|14|15|16 |17|18|19|20|21|
+|p1|p2|1|p4|0|0|1|p8|0|1 |1 |1 |0 |1 |0 |p16|1 |1 |0 |1 |1 |
+p1: Covers (positions: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21), so p1 = (1, 0, 1, 0, 1, 0, 0, 1, 0, 1) -> **1**
+p2: Covers (positions: 2, 3, 6,	7, 10, 11, 14, 15, 18, 19) so p2 = (1, 0, 1, 1, 1, 1, 0, 1, 0) -> **0**
+p4: Covers (positions: 4, 5, 6, 7, 12, 13, 14, 15, 20, 21) so p4 = (0, 0, 1, 1, 0, 1, 0, 1, 1) -> **1**
+p8: Covers (positions: 8, 9, 10, 11, 12, 13, 14, 15) so p8 = (0, 1, 1, 1, 0, 1, 0) -> **0**
+p16: Covers (positions: 16, 17, 18, 19, 20, 21) so p16 = (1, 1, 0, 1, 1) -> **0**
+Encoded message with parity bits will be:
+^ 1^ 2^3^ 4^5^6^7^ 8^9^10^11^12^13^14^15^16^17^18^19^20^21^
+| 1| 0|1| 1|0|0|1| 0|0|1 | 1| 1| 0| 1| 0| 0| 1| 1| 0| 1| 1|
+=== Detecting and correcting a single-bit error ===
+We use even parity: each parity group, including its parity bit, must contain an even number of 1s.
+Assume that bit 15 of the encoded message changes from 0 to 1 during transmission.
+The receiver checks all parity groups again:
+^ Parity check ^ Number of 1s ^ Result ^ Syndrome bit ^
+| p1  | 7 | Odd: error detected  | s1 = 1  |
+| p2  | 7 | Odd: error detected  | s2 = 1  |
+| p4  | 7 | Odd: error detected  | s4 = 1  |
+| p8  | 5 | Odd: error detected  | s8 = 1  |
+| p16 | 4 | Even: check passed  | s16 = 0 |
+Write the syndrome bits in descending order of their position weights:
+  s16 s8 s4 s2 s1 = 0 1 1 1 1
+The binary number 01111 equals decimal 15. Therefore, the error is at position **15**.
+Equivalently, add the position weights of the failed checks:
++ 2 + 4 + 8 = 15
+The receiver corrects the error by changing bit 15 back from **1 to 0**.
+This correction assumes that only one bit has changed.