Binary Huffman Code in C++

Huffman code is an optimal code for the given source (probability distribution), which assigns small length codes to high frequent symbols. For more information click here.

GenHuffmanCode.cpp

#include "MinPriorityQueue.cpp"

using namespace std;

class Node {
public:
    string name;
    int f;
    Node *left, *right;
    string code;

    Node() {
        name = "";
        code = "";
        f = INT_MAX;
        left = right = 0;
    }

    Node(int ff, string n = "") {
        name = n;
        f = ff;
        left = right = 0;
        code = "";
    }

    ~Node() {
        delete left;
        delete right;
    }

    bool operator<(Node &param) {
        return f < param.f;
    }

    bool operator>(Node &param) {
        return f > param.f;
    }

    bool operator==(Node &param) {
        return f == param.f;
    }

    static void display(Node*, bool);
    static void encode(Node*);

    friend ostream& operator <<(ostream&, Node&);
};

void Node::display(Node* node, bool leavesOnly = 1) {
    if (node == 0) {
        return;
    }
    display(node->left, leavesOnly);
    if (leavesOnly) {
        if (node->left == 0 && node->right == 0) {
            cout << *node << ", ";
        }
    } else {
        cout << *node << ", ";
    }
    display(node->right, leavesOnly);
}

void Node::encode(Node* node) {
    if (node == 0) {
        return;
    }
    if (node->left != 0) {
        node->left->code = node->code + "0";
    }
    if (node->right != 0) {
        node->right->code = node->code + "1";
    }
    encode(node->left);
    encode(node->right);
}

ostream& operator <<(ostream &out, Node &node) {
    out << node.name << "(" << node.f << ")" << ":" << node.code;
    return out;
}

void HuffmanCode(int *freqs, string* names, int length) {
    Q<Node> *q = new Q<Node > (length);
    for (int i = 0; i < length; i++) {
        q->insert(new Node(freqs[i], names[i]));
    }

    for (int i = 0; i < length - 1; i++) {
        Node *x = q->extractMin();
        Node *y = q->extractMin();
        Node *z = new Node(x->f + y->f, x->name + y->name);
        z->left = x;
        z->right = y;
        q->insert(z);
    }
    Node *root = q->extractMin();
    cout << "Full tree (inorder):\n";
    Node::display(root, 0);
    cout << "\nHuffman Code:\n";
    Node::encode(root);
    Node::display(root);
}

int main(int argc, char** argv) {
    int freqs[] = {45, 13, 12, 16, 9, 5};
    string names[] = {"a", "b", "c", "d", "e", "f"};
    HuffmanCode(freqs, names, 6);
    return 0;
}

Output

Full tree (inorder):
a(45):, acbfed(100):, c(12):, cb(25):, b(13):, cbfed(55):, f(5):, fe(14):, e(9):, fed(30):, d(16):, 
Huffman Code:
a(45):0, c(12):100, b(13):101, f(5):1100, e(9):1101, d(16):111, 

Minimum Priority Queue Implemented Using Min-Heap in C++

MinPriorityQueue.h

#ifndef MINPRIORITYQUEUE_H
#define MINPRIORITYQUEUE_H

template<class T> class Q {
    int array_size, heap_size;
    T** A; // pointer for the array    

public:
    Q(int s);
    ~Q();
    bool isEmpty();
    bool isFull();
    T** getArray();
    int getArraySize();
    T* minimum();
    T* extractMin();
    bool insert(T*);

private:
    int left(int i);
    int right(int i);
    int parent(int i);
    void decreaseKey(int, T*);
    void minHeapify(int);
};

#endif /* MINPRIORITYQUEUE_H */

MinPriorityQueue.cpp

#include <cstdlib>
#include <iostream>
#include "MinPriorityQueue.h"

using namespace std;

template<class T> Q<T>::Q(int s) {
    array_size = s;
    heap_size = -1;
    A = new T*[s];
}

template<class T> Q<T>::~Q() {
    delete A;
}

template<class T> bool Q<T>::isEmpty() {
    return heap_size < 0;
}

template<class T> bool Q<T>::isFull() {
    return heap_size >= array_size - 1;
}

template<class T> T** Q<T>::getArray() {
    return A;
}

template<class T> int Q<T>::getArraySize() {
    return array_size;
}

template<class T> T* Q<T>::minimum() {
    return A[0];
}

template<class T> int Q<T>::left(int i) {
    return 2 * (i + 1) - 1;
}

template<class T> int Q<T>::right(int i) {
    return 2 * (i + 1);
}

template<class T> int Q<T>::parent(int i) {
    return max((i + 1) / 2 - 1, 0);
}

template<class T> T* Q<T>::extractMin() {
    if (isEmpty()) {
        cout << "Underflow...\n";
        T* t;
        return t;
    } else {
        T* min = A[0];
        A[0] = A[heap_size];
        heap_size--;
        minHeapify(0);
        return min;
    }
}

template<class T> void Q<T>::minHeapify(int i) {
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l <= heap_size && ((*(A[l])) < (*(A[i])))) {
        smallest = l;
    }
    if (r <= heap_size && ((*(A[r])) < (*(A[smallest])))) {
        smallest = r;
    }
    if (smallest != i) {
        T* t = A[i];
        A[i] = A[smallest];
        A[smallest] = t;
        minHeapify(smallest);
    }
}

template<class T> bool Q<T>::insert(T* key) {
    if (isFull()) {
        cout << "Overflow...\n";
        return false;
    } else {
        heap_size++;
        decreaseKey(heap_size, key);
        return true;
    }
}

template<class T> void Q<T>::decreaseKey(int i, T* key) {
    A[i] = key;
    while ((i > 0) && ((*(A[parent(i)])) > (*(A[i])))) {
        T* t = A[i];
        A[i] = A[parent(i)];
        A[parent(i)] = t;
        i = parent(i);
    }
}

TestMinPriorityQueue.cpp

#include "MinPriorityQueue.cpp"

using namespace std;

void testMinPQ() {
    Q<int> *q = new Q<int>(10);
    int x[] = {10, 5, 8, 15, 4, 20, 28, 33, 11, 3};
    for (int i = 0; i < 10; i++) {
        q->insert(&x[i]);
    }
    for (int i = 0; i < 10; i++) {
        cout << (*q->extractMin()) << ", ";
    }
}

int main(int argc, char** argv) {
    testMinPQ();
    return 0;
}

Output

3, 4, 5, 8, 10, 11, 15, 20, 28, 33,

Lowest Common Multiplier and Greatest Common Divisor in Python

Lowest Common Multiplier (LCM) and Greatest Common Divisor (GCD) can be found for any list of numbers by this code. 
LCM x GCD = FACT(x1,x2,...xn)
Here, FACT(x1,x2,...xn) is the multiplication of the input arguments x1 to xn. I used the above equation to find the GCD by calculating LCM first. However, you can calculate GCD directly using Euclid's algorithm.

Code

def lcm(x,y):
    tmp=x
    while (tmp%y)!=0:
        tmp+=x
    return tmp

def lcmm(*args):
    return reduce(lcm,args)

def fact(args):
    if len(args) == 0:
        return 1
    else:
        return args[0] * fact(args[1:])

def gcd(args):
    return fact(args)/lcmm(*args)

args=range(1,11)
print args
print 'LCM:', lcmm(*args)
print 'GCD:', gcd(args)

Euclid's Algorithm

def gcd(a, b):
    while b:      
        a, b = b, a % b
    return a

Question

Find the sequence of numbers whose remainder is one less than its divisor?
Eg. Consider N, N mod x = x - 1 for x in list 1 - 20. Find the sequence of N?

Ans. Find the LCM of list 1 - 20, then N = k * LCM - 1, where k is an integer.

Pseudo Random Sequence Generator in Verilog

Pseudo Random Sequence is widely used in spread spectrum communication, to spread and de-spread the information sequence. The following diagram shows a PN sequence generator which has 3 memory elements, leads to processing gain 7 (2^3 - 1). According to the diagram, if the initial state is all zero, then the sequence will also be all zeros which is not usable.

Behavioural Model

module PNSeqGen(
    input clk, reset,
    output s3
    );
reg s1, s2, s3;
wire s0;
// MODULO 2 ADDITION
assign s0 = s1 ^ s3;
// STATE MACHINE
always @ (posedge clk or reset) begin
// INITIAL STATE SHOULDN'T BE 000 => 100
if(reset) begin
s1 <= 1;
s2 <= 0;
s3 <= 0;
end else begin
s1 <= s0;
s2 <= s1;
s3 <= s2;
end
end
endmodule

Test Bench

`timescale 1ns / 1ps
module Test_PNSeqGen;
// Inputs
reg clk;
reg reset;
// Outputs
wire s3;
// Instantiate the Unit Under Test (UUT)
PNSeqGen uut (
.clk(clk), 
.reset(reset), 
.s3(s3)
);
initial begin
// Initialize Inputs
clk = 0;
reset = 0;
// Wait 100 ns for global reset to finish
#100;
// Add stimulus here
#10 reset = 1;
#10 reset = 0;
#200 $finish;
end
always begin
#5 clk = ~clk;
end
// PRINT SEQUENCE
always @ (posedge clk) $write("%b",s3);      
endmodule

Output

001110100111010011101

4 Bit Priority Encoder in Verilog

Priority Encoder is an encoder circuit that includes a priority function. The operation is such that if two or more inputs are equal to 1 at the same time, the input having the highest priority will take precedence. 
Here, the priority decreases from right to left in the input. D[3] has the highest priority. V indicate the validity of the input (atleast one input should be 1) and the Y gives the output.(01 means 1, 10 means 2 like that...)

Behavioural Model : 4 Bit Priority Encoder

module PriorityEncoder_4Bit(
    input [0:3] D,
    output [1:0] Y,
    output V
    );
reg [1:0] Y;
reg V;
always @(D)
begin
Y[1] <= D[2] | D[3];
Y[0] <= D[3] | D[1] & ~D[2];
V = D[0] | D[1] | D[2] | D[3];
end
endmodule

Test Bench : 4 Bit Priority Encoder

module PriorityEncoder_4Bit_Test;
// Inputs
reg [3:0] D;
// Outputs
wire [1:0] Y;
wire V;
// Instantiate the Unit Under Test (UUT)
PriorityEncoder_4Bit uut (
.D(D), 
.Y(Y), 
.V(V)
);
initial begin
// Initialize Inputs
D = 0;
// Wait 100 ns for global reset to finish
#100;        
// Add stimulus here
#10 D = 4'b0000;
#10 D = 4'b1000;
#10 D = 4'b0100;
#10 D = 4'b0010;
#10 D = 4'b0001;
#10 D = 4'b1010;
#10 D = 4'b1111;
end
initial begin
$monitor("time=",$time,, "D=%b : Y=%b V=%b",D,Y,V);
end      
endmodule

Simulation Results

time= 000, D=0000 : Y=00 V=0
time= 120, D=1000 : Y=00 V=1
time= 130, D=0100 : Y=01 V=1
time= 140, D=0010 : Y=10 V=1
time= 150, D=0001 : Y=11 V=1
time= 160, D=1010 : Y=10 V=1
time= 170, D=1111 : Y=11 V=1