Experiment 1: Parity Check

Objectives

  1. Develop a program to check the integrity of data using a parity bit.
  2. Become familiar with C programming, some bit- wise operations, compilation and testing a program.

Background

In this experiment we’ll check the parity of received data stored in a file. The basic idea is explained using the following example. Suppose that we want to check parity for the following received bits: b=10100100. It is more practical to work with hexadecimal notation rather than decimal. Each hexadecimal digit corresponds to 4 bits. In C we can denote hexadecimal constants by adding the prefix 0x to the hexadecimal number. The corresponding hexadecimal number is b = 0xA4. Parity can be checked by calculating another parity bit for the received word. If this second parity bit is zero, that means that the total number of ones in the received word is even and no errors are detected. Otherwise an error is detected. For the value of b given in this example an error should be detected. The steps to check parity are listed below:

  1. Initialize two working variables as follows: parity will hold the calculated parity of the number and can be either 0 or 1. tmp initially holds the original number:

    parity = 0;
    tmp = number;
    
  2. Use the xor operation (^ in C notation) to perform the modulo-2 sum of all bits in tmp. We perform this operation one bit at a time bit adding parity to the least significant bit (LSB) of tmp as follows:

    while (tmp) {
      parity = parity ^ (tmp & 1);
      tmp = (tmp >> 1);
    }
    

    The & symbol performs the bitwise and operation. It is used to select only the LSB from tmp (otherwise we would be including all other bits). The line with (tmp >> 1) shifts the bits of tmp to the right, discarding the LSB. The loop ends when tmp is zero and there are no more ones to add.

All working variables in this calculation will be declared as unsinged int. On the computers we’ll be performing this experiment, this data type allows us to handle at least 32 bits (or 64) at a time (i.e., at least 8 hexadecimal digits). The printf format string that we’ll use is “%x” to print unsigned integers in hexadecimal format.

A sample code that uses this approach to generate codewords with a parity bit on the left is included in the Appendix Section.

References

  • Class notes on parity bit theory.
  • MinGW (gcc compiler and utilities on Windows): http://mingw.org/

Procedure

  1. Open a command window (cmd.exe). The current directory should be set to c:\users\engineer. Run experiment1 in that window as shown below. That script sets up the working directory and the environment variables to use the compiler. Do not close this window: you need it to compile and run the program.

  2. We’ll assume in the following that the work directory is c:\users\engineering\exp1_2018-09-01 and the source code file is saved as add_parity.c. Your directory name may not be exactly the same but that should not be a problem. Type notepad++ add_parity.c to simultaneously open the notepad++ editor and create the source code file (answer yes to create new file). Paste the code from the Appendix into the editor and save into the work directory. Also set language to C in Notepad++ editor. Save your file.

  3. Return to the command line window. Typing dir should list your saved C source file. Compile the program as shown below. The -Wall option tells the compiler to print all warnings. This is useful to detect problems with the source code. The executable file is called a.exe by default. You can change this name by using the -o flag when compiling. For example:

    gcc -Wall -o add_parity.exe add_parity.c
    

    Every time you make changes to the source code you must re-compile.

  4. Run the program and enter some numbers to encode. Remember, the encoded bits must fit in 32 bits so the maximum result should have 8 hexadecimal digits or less. You can stop the program by typing c while holding the Ctrl key (Ctrl-c).

    Environment setup, compilation of source code using MinGW and program running.

    Note that the printed values alternate between your inputs and the corresponding codewords. This arrangement does not seem convenient for interactive use but it is useful to process long lists of values as described below.

  5. The code can be run more conveniently by redirecting the standard input to a file with numbers. This means that the program reads the input from a file instead of the keyboard. Open a new file in notepad++, type the numbers shown below and save the file as data.hex in the working directory:

    9
    11
    1a3
    0
    

    Now run the code as shown below:

    add_parity.exe < data.hex
    

    Show the output of this command in your report.

  6. Open a new source code file in notepad++ named parity_check.c. Paste the template provided at the end of the Appendix Section to create a program to check codewords sent from standard input with CRC bits and print the ones that are incorrect. The input file is just a list of codewords in hexadecimal format. For example:

    12
    22
    347
    0
    

    Hint: The body of check_parity() could be based on a modification of add_parity(). Once you have an initial running version of your program, test your code with a single inputs first.

    The lab instructor will provide a different list of words to each group. Some of the words contain errors to be detected.

Report preparation and questions

  1. Prepare a printed report summarizing this experiment and submit it to the lab instructor (one report per group).
  2. Include a copy of your decoder source code in your report and explain what modifications were necessary. Your source code should be properly indented, with updated comments and consistent variables and function names.
  3. Create a table: one row per iteration, one column per variable. The table shows the values of the variables (in binary format) for the first 3 iterations of the loop in your implementation of the check_parity() function. The initial data is the first word in the file provided by the lab instructor.
  4. Show the output generated by your program.
  5. Comment difficulties (if any) and conclusions about this experiment.

Appendix

Source code to generate codewords:

/*
This program generates a list of codewords with a parity bit on the
LSB position given a list of data words in hexadecimal format.

Sample usage:

     add_parity < data.txt

prints a list of codewords to standard output. Each line in data.txt
must contain an hexadecimal value (at most 8 digits, the "0x" prefix
is not needed).
*/

#include <stdio.h>

// Calculate parity and insert parity as the LSB in codeword given
// info bits (i)
unsigned int add_parity(unsigned int i)
{
  unsigned int parity, tmp;

  parity = 0;
  tmp = i;
  while (tmp) {
    parity = parity ^ (tmp & 1);
    tmp = (tmp >> 1);
  }
  // Make space in i and add parity
  return (i<<1) + parity;
}


int main()
{
  // i: info bits
  // b: codeword
  unsigned int i,b;

  /* read information bits and encode until end of file */
  while (scanf("%x", &i) != EOF) {
    b = add_parity(i);
    printf("%x\n", b);
  }
  return 0;
}

Parity-check template:

/*
   Parity checker: prints a message when error detected
   --------------
*/
#include <stdio.h>
#include <stdlib.h>

/* Returns parity of word to be checked (b) */
unsigned int check_parity(unsigned int b)
{
  /* add code here */
}


int main()
{
  unsigned int b, line;

  /* read information bits and encode until end of file */
  line = 0;
  while (scanf("%x", &b) != EOF) {
    line++;
    if (check_parity(b))
      printf("Error detected at line %d : 0x%x\n", line, b);
  }
  return 0;
}