(4,3)-Single Parity Check of Binary Sequence Skew Tent and PWL Map

0. Note

This is the fourth assignment from my Masters Applied Digital Information Theory Course which has never been published anywhere and I, as the author and copyright holder, license this assignment customized CC-BY-SA where anyone can share, copy, republish, and sell on condition to state my name as the author and notify that the original and open version available here.

1. Introduction

On Figure 1 of Shannon Communication Model, the previous assignments on memoryless and Markov's source is on the first block transmitter (source), while this fourth assignment is on the channel coding and decoding. It will be demonstrated a binary source coded with parity check codes , going through a noisy channel with the specified bit error rate, and decoded on with parity check. On the receiver side will compare the theoretical and practical error using parity check.

Figure 1. Shannon Communication Model

A parity (3,4) check coding takes 3 bits + 1 into 1 block with the last bit as the parity bit obtained by performing exclusive or (xor) on the 3 bits. The blocks are then transmitted and xor is again performed on the decoder side on the 4 bits of the block, and if the result is 0 then it's not regarded as error, but if the result is 1 then it's regarded as error. Looking this checking method it can detect errors when odd numbers of bits error occurs, but it cannot detect when even number of error occurs. This can be demonstrated on the following table.

Table 1. Parity Check Examples

Information	110	100	101
Code Words	1100 (1⊕1⊕0→0)	1001 (1⊕0⊕0→1)	1010 (1⊕0⊕1→0)
Errors	0000	0100	0011
Received	1100 (1100⊕0000)	1101 (1001⊕0100)	1001 (1010⊕0011)
Judgement	1⊕1⊕0⊕0=0 (no error) correct	1⊕1⊕0⊕1=1 (error) correct	1⊕0⊕0⊕1=0 (no error) wrong

2. Skew Tent Map

The binary sequence on the transmitter is generated by means of 2nd assignment of skew tent map with initial x[1] = 0.1 and c = 0.499999. This time we generated in a million blocks with each blocks contains 3 + 1 bits. On the source we generated the initial bits of normal means on assignment 2, but then we slip a parity bit on every 4th increments of the sequence (on the actual code we made 2 sequence where the first sequence as a reference for the sequence with parity bit, b2[0] = b1[0], b2[1] = b1[1], b2[2] = b1[2], b2[3] = b1[0]⊕b1[1]⊕b1[2], b2[4] = b1[3], b2[5] = b1[4], b2[6] = b1[5], b2[7] = b1[3]⊕b1[4]⊕b1[5], and so on).

After that we simulate an error sequence with initial x_err[0] = 0.500001, error probability p varies, and c_err = 1-p. Then as per section 1 we xor the parity coded binary sequence with the error simulated generated sequence, obtaining the binary sequence at the receiver. We can find the total errors by comparing the binary sequence on the transmitter side (before xor by error sequence) and on the receiver side (after xor by error sequence). Then we perform xor on each blocks (every 4 bits) of the receiver binary sequence to get the detected error. Finally we calculate the difference between total errors (real) and detected error to find the practical undetected error. The theoretical undetected error can be calculated using the following equation: P_u = 6p²(1-p)²+p⁴ which is actually a formula of the probability of even blocks after passing through noisy channel with defined error probability.

Table 2. Trials of Error Probability to Undetected Error

p	0.01	0.05	0.1	0.24	0.49	0.73
Total Error	39348	185428	344862	653470	934984	997957
Detected Error	39167	171220	295457	445080	497971	500982
Undetected Error	181	14208	49405	208390	437013	496975
P Total Error	0.039348	0.185428	0.344862	0.65347	0.934984	0.997957
P Detected Error	0.039167	0.17122	0.295457	0.44508	0.497971	0.500982
P UndetectedError	0.000181	0.014208	0.049405	0.20839	0.437013	0.496975
P UndetectedError Theory	0.00058807	0.0135438	0.0487	0.202936	0.432348	0.517073

3. PWL Map

Roughly similar to 2nd section but this time use PWL Map error sequence. We start by choosing p2, but generating the error sequence we defined c_err as 1-p (initial c remain 0.499999 and p1 is computed), with p2 still the same, but p1_err is defined based on c_err. Automatically slop a changes and the sequence was generated. The process is the same after that, with the theoretical of undetected error as Pu = P(0)((1-p1)p1(1-p2)+p1(1-p2)p2+p1p2p1) + p(1)(p2(1-p1)p1+p2p1p2+(1-p2)p2(1-p1)+(1-p2)(1-p2)(1-p2)), again is actually a formula of even blocks probability after passing through noisy channel with defined error probability.

Table 3. Probability of Practical Undetected Error of different values of p to values of p2

p2\p	0.01	0.05	0.1	0.24	0.49	0.73
0.2	0.028872	0.039856	0.075678	0.187323	0.429819	0.575357
0.4	0.005627	0.040695	0.076027	0.178473	0.40059	0.491026
0.6	0.005245	0.030903	0.07767	0.202801	0.474428	-
0.8	0.000957	0.0247	0.059482	0.202483	0.653459	-

Table 4. Probability of Theoretical Undetected Error of different values of p to values of p2

p2\p	0.01	0.05	0.1	0.24	0.49	0.73
0.2	0.00863918	0.0431779	0.0863013	0.206562	0.415975	0.57224
0.4	0.00792962	0.0398438	0.0801877	0.195824	0.404327	0.426112
0.6	0.00693068	0.0356964	0.0741334	0.198148	0.476694	-
0.8	0.0047017	0.0264344	0.0606124	0.203898	0.654715	-

4. Summary

From above the practical value almost matches the theoretical value. As on Figure 2 plotted based on tables above, for error probability below 0.2 the skew tent map has lower undetected error probability which good to use on channels with little noise. For above it's better to use PWL but with p2 value lower than 0.5.

Figure 2. Probability Error vs Undetected Error Probability

5. Source Code

The source code is divided into 2 one for skew tent map and the other for PWL map written in C++.

//============================================================================
// Name        : skew-tent-map.cpp
// Author      : Fajar Purnama 152-D8713
// Version     : 0.9
// Copyright   : Free to distributed with credits to the author.
// Description : Source Code for Skew Tent Map in C++
//============================================================================

#include 
using namespace std;

int main() {
    cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!

    int N = 10000*3, bin[N]; float x[N], c = 0.499999; x[0] = 0.3;
    // N = number of bits (1 block = 3 bits), c = critical point, x[0] = initial value, x[N] = chaotic sequence, and bin[N] = binary sequence

    // From here is 2nd Assignment
    for (int i = 0; i < N; ++i){
        if (x[i] >= 0 && x[i] < c) {
            x[i+1] = x[i]/c;
            bin[i] = 0;
        } else {
            x[i+1] = (1-x[i])/(1-c);
            bin[i] = 1;
        }
    }
    // Insert bit parity on every 4th bit
    int j = 0, bin_par[N+(N/3)];
    for (int i = 0; i < N+(N/3); i += 4){
        bin_par[i] = bin[j];
        bin_par[i+1] = bin[j+1];
        bin_par[i+2] = bin[j+2];
        bin_par[i+3] = bin_par[i]^bin_par[i+1]^bin_par[i+2];
        j += 3;
    }

    // Generate error sequence
    int bin_err[N+(N/3)]; float p;
    cout << "Enter error probability: "; cin >> p;
    float c_err = 1-p, x_err[N+(N/3)]; x_err[0]=0.500001;
    for (int i = 0; i < N+(N/3); ++i){
        if (x_err[i] >= 0 && x_err[i] < c_err) {
            x_err[i+1] = x_err[i]/c_err;
            bin_err[i] = 0;
        } else {
            x_err[i+1] = (1-x_err[i])/(1-c_err);
            bin_err[i] = 1;
        }
    }

    // Generate receiver side = parity sequence XOR error sequence
    int bin_r[N+(N/3)];
    for (int i = 0; i < N+(N/3); ++i){
        bin_r[i] = bin_par[i] ^ bin_err[i];
    }

    for (int i = 0; i < N+(N/3); ++i){
        cout << bin_err[i];
    }
    cout << endl;
    for (int i = 0; i < N+(N/3); ++i){
        cout << bin_par[i];
    }
    cout << endl;
    for (int i = 0; i < N+(N/3); ++i){
        cout << bin_r[i];
    }
    cout << endl << endl;
    // total error, detected error, undetected error
    float total_error = 0, detected_error = 0, undetected_error = 0;
    float p_theory = ((6*p*p)*((1-p)*(1-p))+(p*p*p*p));
    for (int i = 0; i < N+(N/3); i += 4){
        if((bin_par[i] != bin_r[i])||(bin_par[i+1] != bin_r[i+1])||(bin_par[i+2] != bin_r[i+2])||(bin_par[i+3] != bin_r[i+3])){
            ++total_error;
        }
        if((bin_r[i]^bin_r[i+1]^bin_r[i+2]^bin_r[i+3])==1){
            ++detected_error;
        }
    }
    undetected_error = total_error - detected_error;
    float p_total_error = total_error/(N/3);
    float p_detected_error = detected_error/(N/3);
    float p_undetected_error = undetected_error/(N/3);
    cout << "total error = " << total_error << endl;
    cout << "detected error = " << detected_error << endl;
    cout << endl;
    cout << "undetected error = " << undetected_error << endl;
    cout << "probability of total error = " << p_total_error << endl;
    cout << "probability of detected error = " << p_detected_error << endl;
    cout << "probability of undetected error = " << p_undetected_error << endl;
    cout << "theory = " << p_theory << endl;
    return 0;
}

//============================================================================
// Name        : 43-single-parity-check-codes-large.cpp
// Author      : Fajar Purnama 152-D8713
// Version     : 0.9
// Copyright   : Free to distributed with credits to the author.
// Description : Source Code for PWL Tent Map in C++
//============================================================================

#include 
using namespace std;

int main() {
        int n;
    cout << "Enter number of blocks: "; cin >> n;
    int N = n*3; float p1, p2, c, c1, c2, d1, d2, a, a1, a2, a3;
    c = 0.499999; cout << "Enter value of p2: "; cin >> p2;
    p1 = (1-c)*p2/c;
    a = 1/(1-(p1+p2));
        int* bin = new int[N]; // need to do this because int main cannot hold large numbers, a stack overflow occurs so need to allocate to new heap
        float* x = new float[N]; x[0] = 0.1;
    // N = number of bits (1 block = 3 bits), c = critical point, x[0] = initial value, x[N] = chaotic sequence, and bin[N] = binary sequence

    // From here is 3rd Assignment
    if (p1+p2 < 1){
    
    c1 = c-(c/a);
    c2 = c+((1-c)/a );
    d1 = c1*(1-c);
    d2 = 1-((1-c2)*c);

    a1 = -c/(c1-d1);
    a2 = a;
    a3 = (c-1)/(d2-c2);

    for (int i = 0; i < N; ++i){
        if (x[i] >= 0 && x[i] < c1) {
            x[i+1] = (a1*(x[i]-d1))+c;
        } else if(x[i] >= c1 && x[i] < c2) {
            x[i+1] = a2*(x[i]-c1);
        } else {
            x[i+1] = (a3*(x[i]-c2))+1;
        }
        if (x[i] < c){
            bin[i] = 0;
        } else {
            bin[i] = 1;
        }
    }
    } else if (p1+p2 > 1){
    
    c1 = c-((c-1)/a);
    c2 = c-(c/a);

    d1 = c1*(1-c);
    d2 = 1-((1-c2)*(1-c));

    a1 = -c/(c1-d1);
    a2 = a;
    a3 = c/(d2-c2);

    for (int i = 0; i < N; ++i){
        if (x[i] >= 0 && x[i] < c1) {
            x[i+1] = (a1*(x[i]-d1))+c;
        } else if(x[i] >= c1 && x[i] < c2) {
            x[i+1] = (a2*(x[i]-c1))+1;
        } else {
            x[i+1] = a3*(x[i]-c2);
        }
        if (x[i] < c){
            bin[i] = 0;
        } else {
            bin[i] = 1;
        }
    }
    } else {
        cout << "you can't do this" << endl;
    }

    // Insert bit parity on every 4th bit
    int j = 0; int* bin_par = new int[N+(N/3)];
    for (int i = 0; i < N+(N/3); i += 4){
        bin_par[i] = bin[j];
        bin_par[i+1] = bin[j+1];
        bin_par[i+2] = bin[j+2];
        bin_par[i+3] = bin_par[i]^bin_par[i+1]^bin_par[i+2];
        j += 3;
    }

    // Generate error sequence
    int* bin_err = new int[N+(N/3)]; float p, p1_err;
    float* x_err = new float[N+(N/3)]; x_err[0]=x[0];
    cout << "Enter error probability :"; cin >> p;
    float c_err = 1-p;
    p1_err = (1-c_err)*p2/c_err;
    a = 1/(1-(p1_err+p2));

    if (p1_err+p2 < 1){
    
    c1 = c_err-(c_err/a);
    c2 = c_err+((1-c_err)/a );
    d1 = c1*(1-c_err);
    d2 = 1-((1-c2)*c_err);

    a1 = -c_err/(c1-d1);
    a2 = a;
    a3 = (c_err-1)/(d2-c2);

    for (int i = 0; i < N+(N/3); ++i){
        if (x_err[i] >= 0 && x_err[i] < c1) {
            x_err[i+1] = (a1*(x_err[i]-d1))+c_err;
        } else if(x_err[i] >= c1 && x_err[i] < c2) {
            x_err[i+1] = a2*(x_err[i]-c1);
        } else {
            x_err[i+1] = (a3*(x_err[i]-c2))+1;
        }
        if (x_err[i] < c_err){
            bin_err[i] = 0;
        } else {
            bin_err[i] = 1;
        }
    }
    } else if (p1_err+p2 > 1){
    
    c1 = c_err-((c_err-1)/a);
    c2 = c_err-(c_err/a);

    d1 = c1*(1-c_err);
    d2 = 1-((1-c2)*(1-c_err));

    a1 = -c_err/(c1-d1);
    a2 = a;
    a3 = c_err/(d2-c2);

    for (int i = 0; i < N+(N/3); ++i){
        if (x_err[i] >= 0 && x_err[i] < c1) {
            x_err[i+1] = (a1*(x_err[i]-d1))+c_err;
        } else if(x_err[i] >= c1 && x_err[i] < c2) {
            x_err[i+1] = (a2*(x_err[i]-c1))+1;
        } else {
            x_err[i+1] = a3*(x_err[i]-c2);
        }
        if (x_err[i] < c_err){
            bin_err[i] = 0;
        } else {
            bin_err[i] = 1;
        }
    }
    } else {
        cout << "you can't do this" << endl;
    }

    // Generate receiver side = parity sequence XOR error sequence
    int* bin_r = new int[N+(N/3)];
    for (int i = 0; i < N+(N/3); ++i){
        bin_r[i] = bin_par[i] ^ bin_err[i];
    }
 
       /* Debugging Purpose
    for (int i = 0; i < N+(N/3); ++i){
        cout << bin_err[i];
    }
    cout << endl;
    for (int i = 0; i < N+(N/3); ++i){
        cout << bin_par[i];
    }
    cout << endl;
    for (int i = 0; i < N+(N/3); ++i){
        cout << bin_r[i];
    }
    cout << endl << endl; */

    // total error, detected error, undetected error
    float total_error = 0, detected_error = 0, undetected_error = 0;
    float p_theory = (c_err*(((1-p1_err)*p1_err*(1-p2))+(p1_err*(1-p2)*p2)+(p1_err*p2*p1_err)))+((1-c_err)*((p2*(1-p1_err)*p1_err)+(p2*p1_err*p2)+((1-p2)*p2*(1-p1_err))+((1-p2)*(1-p2)*(1-p2))));
    //float p_theory = (c*(((1-p1)*p1*(1-p2))+(p1*(1-p2)*p2)+(p1*p2*p1)))+((1-c)*((p2*(1-p1)*p1)+(p2*p1*p2)+((1-p2)*p2*(1-p1))+((1-p2)*(1-p2)*(1-p2))));

    for (int i = 0; i < N+(N/3); i += 4){
        if((bin_par[i] != bin_r[i])||(bin_par[i+1] != bin_r[i+1])||(bin_par[i+2] != bin_r[i+2])||(bin_par[i+3] != bin_r[i+3])){
            ++total_error;
        }
        if((bin_r[i]^bin_r[i+1]^bin_r[i+2]^bin_r[i+3])==1){
            ++detected_error;
        }
    }
    undetected_error = total_error - detected_error;

    float p_total_error = total_error/(N/3);
    float p_detected_error = detected_error/(N/3);
    float p_undetected_error = undetected_error/(N/3);
    cout << "total error = " << total_error << endl;
    cout << "detected error = " << detected_error << endl;
    cout << endl;
    cout << "undetected error = " << undetected_error << endl;
    cout << "probability of total error = " << p_total_error << endl;
    cout << "probability of detected error = " << p_detected_error << endl;
    cout << "probability of undetected error = " << p_undetected_error << endl;
    cout << "theory = " << p_theory << endl;

    return 0;
}

Mirrors

• https://www.publish0x.com/fajar-purnama-academics/43-single-parity-check-of-binary-sequence-skew-tent-and-pwl-xxwvokk?a=4oeEw0Yb0B&tid=hive
• https://0darkking0.blogspot.com/2021/01/43-single-parity-check-of-binary.html
• https://0fajarpurnama0.medium.com/4-3-single-parity-check-of-binary-sequence-skew-tent-and-pwl-map-d1697277cec5
• https://0fajarpurnama0.github.io/masters/2020/09/14/single-parity-check-binary-sequence-skew-tent-pwl-map
• https://hicc.cs.kumamoto-u.ac.jp/~fajar/masters/single-parity-check-binary-sequence-skew-tent-pwl-map
• https://0fajarpurnama0.wixsite.com/0fajarpurnama0/post/4-3-single-parity-check-of-binary-sequence-skew-tent-and-pwl-map
• http://0fajarpurnama0.weebly.com/blog/43-single-parity-check-of-binary-sequence-skew-tent-and-pwl-map
• https://0fajarpurnama0.cloudaccess.host/index.php/9-fajar-purnama-academics/189-4-3-single-parity-check-of-binary-sequence-skew-tent-and-pwl-map
• https://read.cash/@FajarPurnama/43-single-parity-check-of-binary-sequence-skew-tent-and-pwl-map-0e025925
• https://www.uptrennd.com/post-detail/4-3-single-parity-check-of-binary-sequence-skew-tent-and-pwl-map~ODU0OTUw