viterbi.java

卷积码就是一种较好的信道编码方式。这种编码方式同样是把k个信息比特编成n个比特

/*
 * Viterbi.java
 * Toy Viterbi Decorder
 *
 * by Yusuke Shinyama <yusuke at cs . nyu . edu>
 *
 *   Permission to use, copy, modify, distribute this software 
 *   for any purpose is hereby granted without fee, provided 
 *   that the above copyright notice appear in all copies and
 *   that both that copyright notice and this permission notice
 *   appear in supporting documentation.
 */

import java.awt.*;
import java.util.*;
import java.text.*;
import java.awt.event.*;
import java.applet.*;


class Symbol {
    public String name;

    public Symbol(String s) {
	name = s;
    }
}

class SymbolTable {
    Hashtable table;

    public SymbolTable() {
	table = new Hashtable();
    }
    public Symbol intern(String s) {
	s = s.toLowerCase();
	Object sym = table.get(s);
	if (sym == null) {
	    sym = new Symbol(s);
	    table.put(s, sym);
	}
	return (Symbol)sym;
    }
}

class SymbolList {
    Vector list;

    public SymbolList() {
	list = new Vector();
    }
    public int size() {
	return list.size();
    }
    public void set(int index, Symbol sym) {
	list.setElementAt(sym, index);
    }
    public void add(Symbol sym) {
	list.addElement(sym);
    }
    public Symbol get(int index) {
	return (Symbol) list.elementAt(index);
    }
}

class IntegerList {
    Vector list;

    public IntegerList() {
	list = new Vector();
    }
    public int size() {
	return list.size();
    }
    public void set(int index, int i) {
	list.setElementAt(new Integer(i), index);
    }
    public void add(int i) {
	list.addElement(new Integer(i));
    }
    public int get(int index) {
	return ((Integer)list.elementAt(index)).intValue();
    }
}

class ProbTable {
    Hashtable table;
    
    public ProbTable() {
	table = new Hashtable();
    }
    public void put(Object obj, double prob) {
	table.put(obj, new Double(prob));
    }
    public double get(Object obj) {
	Double prob = (Double)table.get(obj);
	if (prob == null) {
	    return 0.0;
	}
	return prob.doubleValue();
    }
    // normalize probability
    public void normalize() {
	double total = 0.0;
	for(Enumeration e = table.elements() ; e.hasMoreElements() ;) {
	    total += ((Double)e.nextElement()).doubleValue();
	}
	if (total == 0.0) {
	    return;		// div by zero!
	}
	for(Enumeration e = table.keys() ; e.hasMoreElements() ;) {
	    Object k = e.nextElement();
	    double prob = ((Double)table.get(k)).doubleValue();
	    table.put(k, new Double(prob / total));
	}
    }
}

class State {
    public String name;
    ProbTable emits;
    ProbTable linksto;
    
    public State(String s) {
	name = s;
	emits = new ProbTable();
	linksto = new ProbTable();
    }
    
    public void normalize() {
	emits.normalize();
	linksto.normalize();
    }

    public void addSymbol(Symbol sym, double prob) {
	emits.put(sym, prob);
    }
    
    public double emitprob(Symbol sym) {
	return emits.get(sym);
    }

    public void addLink(State st, double prob) {
	linksto.put(st, prob);
    }

    public double transprob(State st) {
	return linksto.get(st);
    }
}

class StateTable {
    Hashtable table;

    public StateTable() {
	table = new Hashtable();
    }
    public State get(String s) {
	s = s.toUpperCase();
	State st = (State)table.get(s);
	if (st == null) {
	    st = new State(s);
	    table.put(s, st);
	}
	return st;
    }
}

class StateIDTable {
    Hashtable table;
    
    public StateIDTable() {
	table = new Hashtable();
    }
    public void put(State obj, int i) {
	table.put(obj, new Integer(i));
    }
    public int get(State obj) {
	Integer i = (Integer)table.get(obj);
	if (i == null) {
	    return 0;
	}
	return i.intValue();
    }
}

class StateList {
    Vector list;

    public StateList() {
	list = new Vector();
    }
    public int size() {
	return list.size();
    }
    public void set(int index, State st) {
	list.setElementAt(st, index);
    }
    public void add(State st) {
	list.addElement(st);
    }
    public State get(int index) {
	return (State) list.elementAt(index);
    }
}

class HMMCanvas extends Canvas {
    static final int grid_x = 60;
    static final int grid_y = 40;
    static final int offset_x = 70;
    static final int offset_y = 30;
    static final int offset_y2 = 10;
    static final int offset_y3 = 65;
    static final int col_x = 40;
    static final int col_y = 10;
    static final int state_r = 10;
    static final Color state_fill = Color.white;
    static final Color state_fill_maximum = Color.yellow;
    static final Color state_fill_best = Color.red;
    static final Color state_boundery = Color.black;
    static final Color link_normal = Color.green;
    static final Color link_processed = Color.blue;
    static final Color link_maximum = Color.red;
    
    HMMDecoder hmm;
    
    public HMMCanvas() {
	setBackground(Color.white);
	setSize(400,300);
    }
    
    public void setHMM(HMMDecoder h) {
	hmm = h;
    }

    private void drawState(Graphics g, int x, int y, Color c) {
	x = x * grid_x + offset_x;
	y = y * grid_y + offset_y;
	g.setColor(c);
	g.fillOval(x-state_r, y-state_r, state_r*2, state_r*2);
	g.setColor(state_boundery);
	g.drawOval(x-state_r, y-state_r, state_r*2, state_r*2);
    }
    
    private void drawLink(Graphics g, int x, int y0, int y1, Color c) {
	int x0 = grid_x * x + offset_x;
	int x1 = grid_x * (x+1) + offset_x;
	y0 = y0 * grid_y + offset_y;
	y1 = y1 * grid_y + offset_y;
	g.setColor(c);
	g.drawLine(x0, y0, x1, y1);
    }

    private void drawCenterString(Graphics g, String s, int x, int y) {
	x = x - g.getFontMetrics().stringWidth(s)/2;
	g.setColor(Color.black);
	g.drawString(s, x, y+5);
    }

    private void drawRightString(Graphics g, String s, int x, int y) {
	x = x - g.getFontMetrics().stringWidth(s);
	g.setColor(Color.black);
	g.drawString(s, x, y+5);
    }

    public void paint(Graphics g) {
	if (hmm == null) {
	    return;
	}
	DecimalFormat form = new DecimalFormat("0.0000");
	int nsymbols = hmm.symbols.size();
	int nstates = hmm.states.size();
	// complete graph.
	for(int i = 0; i < nsymbols; i++) {
	    int offset_ymax = offset_y2+nstates*grid_y;
	    if (i < nsymbols-1) {
		for(int y1 = 0; y1 < nstates; y1++) {
		    for(int y0 = 0; y0 < nstates; y0++) {
			Color c = link_normal;
			if (hmm.stage == i+1 && hmm.i0 == y0 && hmm.i1 == y1) {
			    c = link_processed;
			}
			if (hmm.matrix_prevstate[i+1][y1] == y0) {
			    c = link_maximum;
			}
			drawLink(g, i, y0, y1, c);
			if (c == link_maximum && 0 < i) {
			    double transprob = hmm.states.get(y0).transprob(hmm.states.get(y1));
			    drawCenterString(g, form.format(transprob),
					     offset_x + i*grid_x + grid_x/2, offset_ymax);
			    offset_ymax = offset_ymax + 16;
			}
		    }
		}
	    }
	    // state circles.
	    for(int y = 0; y < nstates; y++) {
		Color c = state_fill;
		if (hmm.matrix_prevstate[i][y] != -1) {
		    c = state_fill_maximum;
		}
		if (hmm.sequence.size() == nsymbols && 
		    hmm.sequence.get(nsymbols-1-i) == y) {
		    c = state_fill_best;
		}
		drawState(g, i, y, c);
	    }
	}
	// max probability.
	for(int i = 0; i < nsymbols; i++) {
	    for(int y1 = 0; y1 < nstates; y1++) {
		if (hmm.matrix_prevstate[i][y1] != -1) {
		    drawCenterString(g, form.format(hmm.matrix_maxprob[i][y1]),
				     offset_x+i*grid_x, offset_y+y1*grid_y);
		}
	    }
	}
	
	// captions (symbols atop)
	for(int i = 0; i < nsymbols; i++) {
	    drawCenterString(g, hmm.symbols.get(i).name, offset_x+i*grid_x, col_y);
	}
	// captions (states in left)
	for(int y = 0; y < nstates; y++) {
	    drawRightString(g, hmm.states.get(y).name, col_x, offset_y+y*grid_y);
	}

	// status bar
	g.setColor(Color.black);
	g.drawString(hmm.status, col_x, offset_y3+nstates*grid_y);
	g.drawString(hmm.status2, col_x, offset_y3+nstates*grid_y+16);
    }
}

class HMMDecoder {
    StateList states;
    int state_start;
    int state_end;

    public IntegerList sequence;
    public double[][] matrix_maxprob;
    public int[][] matrix_prevstate;
    public SymbolList symbols;
    public double probmax;
    public int stage, i0, i1;
    public boolean laststage;
    public String status, status2;
    
    public HMMDecoder() {
	status = "Not initialized.";
	status2 = "";
	states = new StateList();
    }
    
    public void addStartState(State st) {
	state_start = states.size(); // get current index
	states.add(st);
    }
    public void addNormalState(State st) {