Program to Implement Encoder in C++ Assignment Solution

Instructions

Objective

Write a program to implement encoder in c++

Requirements and Specifications

To complete C++ assignment, you will create a multithreaded Shannon-Fano-Elias encoder (https://en.wikipedia.org/wiki/Shannon–Fano–Elias_coding).

To determine the codes for the symbols using the Shannon-Fano-Elias encoder, you must execute the following steps:

1. Arrange the symbols according to decreasing probabilities.
2. Calculate cumulative probability.
3. Calculate modified cumulative distribution function.
4. Find the length of the code.
5. Generate the code word by finding the binary of Fbar(x) with respect to length l(x).

Given the symbols with their probabilities (sorted in decreasing order based on the probability value), you need to implement the Shannon-Fano-Elias encoding algorithm based on the following steps:

• Read the input from STDIN (the Moodle server will implement input redirection to send the information from a file to STDIN). The format of the input file is as follows:

• A string representing the symbols. A single character represents each symbol, and a single white space separates the symbols.
• A list of double values representing the probabilities of the symbols

The symbols from the input are sorted (in decreasing order) based on their probabilities.

Given the previous format, the following file represents a valid input file:

A B C D E

0.3 0.25 0.2 0.15 0.1

• Create n POSIX threads (where n is the number of symbols to encode). Each child thread executes the following tasks:

Receives the probabilities of the symbols from the main thread.

Implements the Shannon-Fano-Elias encoding algorithm to determine the code for the assigned symbol.

Stores the code on a memory location accessible by the main thread.

• Print the Shannon-Fano-Elias codes for the symbols from the input file. Given the previous input, the expected output is:

SHANNON-FANO-ELIAS Codes:

Symbol A, Code: 001

Symbol B, Code: 011

Symbol C, Code: 1010

Symbol D, Code: 1101

Symbol E, Code: 11110

NOTES:

• Not using multiple POSIX threads to implement your solution will translate into a penalty of 100%.
• You must use the output statement format based on the example above.
• You can safely assume that the input will always be valid.

Source Code

#include using namespace std; struct node { string sym; float pro; int arr[20]; int top; } p[20]; typedef struct node node; void shannon(int l, int h, node p[]) { float pack1 = 0, pack2 = 0, diff1 = 0, diff2 = 0; int i, d, k, j; if ((l + 1) == h || l == h || l > h) { if (l == h || l > h) return; p[h].arr[++(p[h].top)] = 0; p[l].arr[++(p[l].top)] = 1; return; } else { for (i = l; i <= h - 1; i++) pack1 = pack1 + p[i].pro; pack2 = pack2 + p[h].pro; diff1 = pack1 - pack2; if (diff1 < 0) diff1 = diff1 * -1; j = 2; while (j != h - l + 1) { k = h - j; pack1 = pack2 = 0; for (i = l; i <= k; i++) pack1 = pack1 + p[i].pro; for (i = h; i > k; i--) pack2 = pack2 + p[i].pro; diff2 = pack1 - pack2; if (diff2 < 0) diff2 = diff2 * -1; if (diff2 >= diff1) break; diff1 = diff2; j++; } k++; for (i = l; i <= k; i++) p[i].arr[++(p[i].top)] = 1; for (i = k + 1; i <= h; i++) p[i].arr[++(p[i].top)] = 0; shannon(l, k, p); shannon(k + 1, h, p); } } void sortByProbability(int n, node p[]) { int i, j; node temp; for (j = 1; j <= n - 1; j++) { for (i = 0; i < n - 1; i++) { if ((p[i].pro) > (p[i + 1].pro)) { temp.pro = p[i].pro; temp.sym = p[i].sym; p[i].pro = p[i + 1].pro; p[i].sym = p[i + 1].sym; p[i + 1].pro = temp.pro; p[i + 1].sym = temp.sym; } } } } void display(int n, node p[]) { int i, j; cout << "\n\n\n\tSymbol\tProbability\tCode"; for (i = n - 1; i >= 0; i--) { cout << "\n\t" << p[i].sym << "\t\t" << p[i].pro << "\t"; for (j = 0; j <= p[i].top; j++) cout << p[i].arr[j]; } } // Driver code int main() { int n, i, j; float total = 0; string ch; node temp; cout << "Enter number of symbols\t: "; n = 5; cout << n << endl; for (i = 0; i < n; i++) { cout << "Enter symbol " << i + 1 << " : "; ch = (char)(65 + i); cout << ch << endl; p[i].sym += ch; } // Input probability of symbols float x[] = { 0.3, 0.25, 0.2, 0.15, 0.1 }; for (i = 0; i < n; i++) { cout << "\nEnter probability of " << p[i].sym << " : "; cout << x[i] << endl; p[i].pro = x[i]; total = total + p[i].pro; // checking max probability if (total > 1) { cout << "Invalid. Enter new values"; total = total - p[i].pro; i--; } } p[i].pro = 1 - total; sortByProbability(n, p); for (i = 0; i < n; i++) p[i].top = -1; shannon(0, n - 1, p); // Display the codes display(n, p); return 0; }