ptolemy.actor.lib.comm
Class ViterbiDecoder

java.lang.Object
  ptolemy.kernel.util.NamedObj
      ptolemy.kernel.InstantiableNamedObj
          ptolemy.kernel.Entity
              ptolemy.kernel.ComponentEntity
                  ptolemy.actor.AtomicActor
                      ptolemy.actor.TypedAtomicActor
                          ptolemy.actor.lib.Transformer
                              ptolemy.actor.lib.comm.ViterbiDecoder

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, Actor, Executable, FiringsRecordable, Initializable, TypedActor, Changeable, Debuggable, DebugListener, Derivable, Instantiable, ModelErrorHandler, MoMLExportable, Moveable, Nameable

Direct Known Subclasses:

TrellisDecoder

public class ViterbiDecoder
extends Transformer

The Viterbi algorithm is an optimal way to decode convolutional and trellis codes. The code is specified jointly by the uncodedRate and polynomialArray parameters. To get a k/n code, set uncodedRate to k and give n integers in polynomialArray. See ConvolutionalCoder for details about the meaning of these parameters. On each firing, this actor will read n inputs and produce k outputs.

The decoder finds the most likely data sequence given noisy inputs by searching all possibilities and computing the distance between the codewords they produce and the observed noisy data. The sequence yielding the minimum distance is the decoded output.

There are two choices offered in this actor to compute the distance. If it the parameter softDecoding is set to be false, the input port will accept boolean tokens and compute the Hamming distance. If the parameter softDecoding is set to be true, the input port will accept double tokens and compute the Euclidean distance. The parameter constellation should be a double array of length 2. The first element specifies the amplitude of "false" input. The second element specifies the amplitude of "true" input. At this time, this actor can only handle binary antipodal constellations, but we expect to generalize this.

Soft decoding has lower probability of decoding error than hard decoding. But distance computation for hard decoding is easier, since it is based on bit operations. Moreover, hard decoding can be used when there is no direct observation of the noisy data, but only observations of a bit sequence that may have errors in it. With hard decoding, this actor serves the role of correcting errors. With soft decoding, it serves the role of reducing the likelyhood of errors.

There is some delay between the reading of input data and the production of decoded output data. That delay, which is called the trace-back depth or truncation depth of the decoder, is controlled by the delay parameter, which is required to be a positive integer. On the first delay firings of this actor, the outputs will be false. On each firing, the number of outputs produced is uncodedRate, so the output will have a prefix of delay*uncodedRate false-valued tokens before any decoded bits are produced. Larger values of delay generally reduce the probability of error. A good rule of thumb is to set delay to five times the highest order of all polynomials, provided that the convolutional code is a one that has good distance properties.

For more information on convolutional codes and Viterbi decoder, see the ConvolutionalCoder actor and Proakis, Digital Communications, Fourth Edition, McGraw-Hill, 2001, pp. 471-477 and pp. 482-485, or Barry, Lee and Messerschmitt, Digital Communication, Third Edition, Kluwer, 2004.

Since:

Ptolemy II 3.0

Version:

$Id: ViterbiDecoder.java 57040 2010-01-27 20:52:32Z cxh $

Author:

Ye Zhou, contributor: Edward A. Lee

See Also:

Serialized Form

Accepted Rating:

Red (cxh)

Proposed Rating:

Yellow (eal)

Nested Class Summary

Nested classes/interfaces inherited from class ptolemy.kernel.Entity

Entity.ContainedObjectsIterator

Field Summary

private int	_colNum
private Complex[]	_constellation
private int	_depth
private boolean	_depthInvalid
private double[]	_distance
private double	_falseAmp
private int	_flag
private static int	_HARD
private int	_inputNumber
private boolean	_inputNumberInvalid
private Parameter	_inputRate
private int[]	_mask
private int	_maskNumber
private int	_maxPolyValue
private int	_mode
private Parameter	_outputRate
private int[][]	_path
private int	_rowNum
private int	_shiftRegLength
private static int	_SOFT
private boolean	_softMode
private double[]	_tempDistance
private int[][]	_tempPath
private static int	_TRELLIS
private boolean	_trellisMode
private double	_trueAmp
private int[][][]	_truthTable
private TypeAttribute	_type
Parameter	constellation The constellation for soft decoding.
Parameter	delay Integer defining the trace back depth of the viterbi decoder.
Parameter	polynomialArray An array of integers defining polynomials with binary coefficients.
Parameter	softDecoding Boolean defining the decoding mode.
Parameter	trellisDecoding Boolean defining whether the decoder will do trellis decoding.
Parameter	uncodedRate Integer defining the number of bits produced at the output in each firing.

Fields inherited from class ptolemy.actor.lib.Transformer

input, output

Fields inherited from class ptolemy.actor.AtomicActor

_actorFiringListeners, _initializables, _notifyingActorFiring, _stopRequested

Fields inherited from class ptolemy.kernel.util.NamedObj

_changeListeners, _changeLock, _changeRequests, _debugging, _debugListeners, _elementName, _isPersistent, _verbose, _workspace, ATTRIBUTES, CLASSNAME, COMPLETE, CONTENTS, DEEP, FULLNAME, LINKS

Fields inherited from interface ptolemy.actor.Executable

COMPLETED, NOT_READY, STOP_ITERATING

Constructor Summary

ViterbiDecoder(CompositeEntity container, java.lang.String name)
Construct an actor with the given container and name.

Method Summary

private int[]	_calculateParity(int[] mask, int maskNumber, int reg) Calculate the parity given by the polynomial and the state of shift register.
private int	_computeHardDistance(boolean[] y, int truthValue, int maskNum) Compute the Hamming distance given by the datum received from the input port and the value in the truthTable.
private double	_computeSoftDistance(double[] y, double falseAmp, double trueAmp, int truthValue, int inputRate) Compute the Euclidean distance given by the datum received from the input port and the value in the truthTable.
private double	_computeTrellisDistance(Complex y, Complex[] constellation, int truthValue) Compute the Euclidean distance given by the datum received from the input port and the value in the truthTable in trellis decoding mode.
private BooleanToken[]	_convertToBit(int integer, int length) Convert an integer to its binary form.
void	attributeChanged(Attribute attribute) If the attribute being changed is softDecoding or trellisDecoding, set input port and constellation type to be complex if trellisDecoding is true; else if softDecoding is true, set them to double type; otherwise set the input port to type boolean.
java.lang.Object	clone(Workspace workspace) Clone the actor into the specified workspace.
void	fire() Read n inputs and produce k outputs, where n is the number of integers in polynomialArray and k is the value of the uncodedRate parameter.
void	initialize() Initialize the actor.
boolean	postfire() Record the datum in buffers into their temporary versions.

Methods inherited from class ptolemy.actor.TypedAtomicActor

_addPort, _fireAt, _fireAt, attributeTypeChanged, clone, newPort, typeConstraintList, typeConstraints

Methods inherited from class ptolemy.actor.AtomicActor

_actorFiring, _actorFiring, addActorFiringListener, addInitializable, connectionsChanged, createReceivers, declareDelayDependency, getCausalityInterface, getDirector, getExecutiveDirector, getManager, inputPortList, isFireFunctional, isStrict, iterate, newReceiver, outputPortList, prefire, preinitialize, pruneDependencies, recordFiring, removeActorFiringListener, removeDependency, removeInitializable, setContainer, stop, stopFire, terminate, wrapup

Methods inherited from class ptolemy.kernel.ComponentEntity

_adjustDeferrals, _checkContainer, _getContainedObject, _propagateExistence, getContainer, instantiate, isAtomic, isOpaque, moveDown, moveToFirst, moveToIndex, moveToLast, moveUp, propagateExistence, setName

Methods inherited from class ptolemy.kernel.Entity

_description, _exportMoMLContents, _removePort, _validateSettables, connectedPortList, connectedPorts, containedObjectsIterator, getAttribute, getPort, getPorts, linkedRelationList, linkedRelations, portList, removeAllPorts, setClassDefinition, uniqueName

Methods inherited from class ptolemy.kernel.InstantiableNamedObj

_setParent, exportMoML, getChildren, getElementName, getParent, getPrototypeList, isClassDefinition, isWithinClassDefinition

Methods inherited from class ptolemy.kernel.util.NamedObj

_addAttribute, _adjustOverride, _attachText, _cloneFixAttributeFields, _debug, _debug, _debug, _debug, _debug, _getIndentPrefix, _isMoMLSuppressed, _markContentsDerived, _propagateValue, _recordDecoratedAttributes, _removeAttribute, _splitName, _stripNumericSuffix, addChangeListener, addDebugListener, attributeList, attributeList, deepContains, depthInHierarchy, description, description, event, executeChangeRequests, exportMoML, exportMoML, exportMoML, exportMoML, exportMoMLPlain, getAttribute, getAttributes, getChangeListeners, getClassName, getDecoratorAttribute, getDecoratorAttributes, getDerivedLevel, getDerivedList, getDisplayName, getFullName, getModelErrorHandler, getName, getName, getSource, handleModelError, isDeferringChangeRequests, isOverridden, isPersistent, lazyContainedObjectsIterator, message, propagateValue, propagateValues, removeChangeListener, removeDebugListener, requestChange, setClassName, setDeferringChangeRequests, setDerivedLevel, setDisplayName, setModelErrorHandler, setPersistent, setSource, sortContainedObjects, toplevel, toString, validateSettables, workspace

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface ptolemy.actor.Actor

createReceivers, getCausalityInterface, getDirector, getExecutiveDirector, getManager, inputPortList, newReceiver, outputPortList

Methods inherited from interface ptolemy.actor.Executable

isFireFunctional, isStrict, iterate, prefire, stop, stopFire, terminate

Methods inherited from interface ptolemy.actor.Initializable

addInitializable, preinitialize, removeInitializable, wrapup

Methods inherited from interface ptolemy.kernel.util.Nameable

description, getContainer, getDisplayName, getFullName, getName, getName, setName

Methods inherited from interface ptolemy.kernel.util.Derivable

getDerivedLevel, getDerivedList, propagateValue

Field Detail

polynomialArray

public Parameter polynomialArray

An array of integers defining polynomials with binary coefficients. The coefficients indicate the presence (1) or absence (0) of a tap in the shift register. Each element of this array parameter should be a positive integer. The default value is {05, 07}.

uncodedRate

public Parameter uncodedRate

Integer defining the number of bits produced at the output in each firing. It should be a positive integer. Its default value is 1.

delay

public Parameter delay

Integer defining the trace back depth of the viterbi decoder. It should be a positive integer. Its default value is the integer 10.

softDecoding

public Parameter softDecoding

Boolean defining the decoding mode. If it is true, the decoder will do soft decoding, and the input data type will be double; otherwise it will do hard decoding, and the input data type will be boolean. The default value is false.

trellisDecoding

public Parameter trellisDecoding

Boolean defining whether the decoder will do trellis decoding. If it is true, the input data and constellation type will be complex; otherwise, they follow the constraints set by softDecoding. This parameter is always set to "false" in ViterbiDecoder. It will always be set to "true" in TrellisDecoder subclass.

constellation

public Parameter constellation

The constellation for soft decoding. Inputs are expected to be symbols from this constellation with added noise. This parameter should be a double array of length 2. The first element defines the amplitude of "false" input. The second element defines the amplitude of "true" input.

_inputRate

private Parameter _inputRate

_outputRate

private Parameter _outputRate

_type

private TypeAttribute _type

_trellisMode

private boolean _trellisMode

_softMode

private boolean _softMode

_mode

private int _mode

_trueAmp

private double _trueAmp

_falseAmp

private double _falseAmp

_constellation

private Complex[] _constellation

_inputNumber

private int _inputNumber

_maskNumber

private int _maskNumber

_mask

private int[] _mask

_maxPolyValue

private int _maxPolyValue

_shiftRegLength

private int _shiftRegLength

_inputNumberInvalid

private transient boolean _inputNumberInvalid

_depthInvalid

private transient boolean _depthInvalid

_truthTable

private int[][][] _truthTable

_rowNum

private int _rowNum

_colNum

private int _colNum

_depth

private int _depth

_distance

private double[] _distance

_tempDistance

private double[] _tempDistance

_path

private int[][] _path

_tempPath

private int[][] _tempPath

_flag

private int _flag

_HARD

private static final int _HARD

See Also:

Constant Field Values

_SOFT

private static final int _SOFT

See Also:

Constant Field Values

_TRELLIS

private static final int _TRELLIS

See Also:

Constant Field Values

Constructor Detail

ViterbiDecoder

public ViterbiDecoder(CompositeEntity container,
                      java.lang.String name)
               throws NameDuplicationException,
                      IllegalActionException

Construct an actor with the given container and name. The output and trigger ports are also constructed.

Parameters:

container - The container.

name - The name of this actor.

Throws:

IllegalActionException - If the entity cannot be contained by the proposed container.

NameDuplicationException - If the container already has an actor with this name.

Method Detail

attributeChanged

public void attributeChanged(Attribute attribute)
                      throws IllegalActionException

If the attribute being changed is softDecoding or trellisDecoding, set input port and constellation type to be complex if trellisDecoding is true; else if softDecoding is true, set them to double type; otherwise set the input port to type boolean. If the attribute being changed is uncodedRate or delay then verify it is a positive integer; if it is polynomialArray, then verify that each of its elements is a positive integer.

Overrides:

attributeChanged in class NamedObj

Parameters:

attribute - The attribute that changed.

Throws:

IllegalActionException - If uncodedRate, or delay is non-positive, or any element of polynomialArray is non-positive.

clone

public java.lang.Object clone(Workspace workspace)
                       throws java.lang.CloneNotSupportedException

Clone the actor into the specified workspace.

Overrides:

clone in class AtomicActor

Parameters:

workspace - The workspace for the new object.

Returns:

A new actor.

Throws:

java.lang.CloneNotSupportedException - If a derived class contains an attribute that cannot be cloned.

See Also:

NamedObj.exportMoML(Writer, int, String), NamedObj.setDeferringChangeRequests(boolean)

fire

public void fire()
          throws IllegalActionException

Read n inputs and produce k outputs, where n is the number of integers in polynomialArray and k is the value of the uncodedRate parameter. The outputs are a decoded bit sequence, with a prefix of false-valued tokens produced on the first delay firings. The number of leading false outputs, therefore, is delay*uncodedRate. To decode, the actor searches iteratively of all possible input sequence and find the one that has the minimum distance to the observed inputs.

Specified by:

fire in interface Executable

Overrides:

fire in class AtomicActor

Throws:

IllegalActionException - Not thrown in this base class.

initialize

public void initialize()
                throws IllegalActionException

Initialize the actor.

Specified by:

initialize in interface Initializable

Overrides:

initialize in class AtomicActor

Throws:

IllegalActionException - If the parent class throws it.

postfire

public boolean postfire()
                 throws IllegalActionException

Record the datum in buffers into their temporary versions.

Specified by:

postfire in interface Executable

Overrides:

postfire in class AtomicActor

Returns:

True if execution can continue into the next iteration.

Throws:

IllegalActionException - If the base class throws it

_calculateParity

private int[] _calculateParity(int[] mask,
                               int maskNumber,
                               int reg)

Calculate the parity given by the polynomial and the state of shift register.

Parameters:

mask - Polynomial.

maskNumber - Number of polynomials.

reg - State of shift register.

Returns:

Parity.

_computeHardDistance

private int _computeHardDistance(boolean[] y,
                                 int truthValue,
                                 int maskNum)

Compute the Hamming distance given by the datum received from the input port and the value in the truthTable.

Parameters:

y - Array of the booleans received from the input port.

truthValue - integer representing the truth value from the truth table.

maskNum - The length of "y" and "truthValue".

Returns:

The distance.

_computeSoftDistance

private double _computeSoftDistance(double[] y,
                                    double falseAmp,
                                    double trueAmp,
                                    int truthValue,
                                    int inputRate)

Compute the Euclidean distance given by the datum received from the input port and the value in the truthTable.

Parameters:

y - Array of the double-type numbers received from the input port.

falseAmp - Amplitude of "false" input.

trueAmp - Amplitude of "true" input.

truthValue - integer representing the truth value from the truth table.

inputRate - The length of "y" and "truthValue".

Returns:

The distance.

_computeTrellisDistance

private double _computeTrellisDistance(Complex y,
                                       Complex[] constellation,
                                       int truthValue)

Compute the Euclidean distance given by the datum received from the input port and the value in the truthTable in trellis decoding mode.

Parameters:

y - Complex number received from the input port.

constellation - Complex array defining the constellation.

truthValue - integer representing the truth value from the truth table.

Returns:

The distance.

_convertToBit

private BooleanToken[] _convertToBit(int integer,
                                     int length)

Convert an integer to its binary form. The bits are stored in an array.

Parameters:

integer - The integer to be converted.

length - The length of "integer" in binary form.

Returns:

The bits of "integer" stored in an array.