ptolemy.actor.lib.comm
Class ViterbiDecoder

java.lang.Object
  extended byptolemy.kernel.util.NamedObj
      extended byptolemy.kernel.InstantiableNamedObj
          extended byptolemy.kernel.Entity
              extended byptolemy.kernel.ComponentEntity
                  extended byptolemy.actor.AtomicActor
                      extended byptolemy.actor.TypedAtomicActor
                          extended byptolemy.actor.lib.Transformer
                              extended byptolemy.actor.lib.comm.ViterbiDecoder
All Implemented Interfaces:
Actor, Changeable, java.lang.Cloneable, Debuggable, DebugListener, Derivable, Executable, Instantiable, ModelErrorHandler, MoMLExportable, Nameable, java.io.Serializable, TypedActor
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,v 1.38 2004/04/13 05:13:10 cxh Exp $
Author:
Rachel Zhou, contributor: Edward A. Lee
See Also:
Serialized Form
Accepted Rating:
Red (cxh)
Proposed Rating:
Yellow (eal)

Nested Class Summary
 
Nested classes inherited from class ptolemy.kernel.Entity
Entity.ContainedObjectsIterator
 
Field Summary
 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
_stopRequested
 
Fields inherited from class ptolemy.kernel.util.NamedObj
_changeListeners, _changeLock, _changeRequests, _debugging, _debugListeners, _elementName, _isPersistent, _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
 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.
 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, attributeTypeChanged, clone, newPort, typeConstraintList
 
Methods inherited from class ptolemy.actor.AtomicActor
_createReceivers, clone, connectionsChanged, getDirector, getExecutiveDirector, getFunctionDependency, getManager, inputPortList, iterate, newReceiver, outputPortList, prefire, preinitialize, pruneDependencies, removeDependency, setContainer, stop, stopFire, terminate, wrapup
 
Methods inherited from class ptolemy.kernel.ComponentEntity
_adjustDeferrals, _checkContainer, _getContainedObject, _propagateExistence, getContainer, instantiate, isAtomic, isOpaque, propagateExistence, setName
 
Methods inherited from class ptolemy.kernel.Entity
_description, _exportMoMLContents, _removePort, connectedPortList, connectedPorts, containedObjectsIterator, getAttribute, getPort, getPorts, linkedRelationList, linkedRelations, portList, removeAllPorts, setClassDefinition, uniqueName, validateSettables
 
Methods inherited from class ptolemy.kernel.InstantiableNamedObj
_setParent, exportMoML, getChildren, getElementName, getParent, getPrototypeList, isClassDefinition
 
Methods inherited from class ptolemy.kernel.util.NamedObj
_addAttribute, _attachText, _cloneFixAttributeFields, _debug, _debug, _debug, _debug, _debug, _getIndentPrefix, _isMoMLSuppressed, _markContentsDerived, _propagateValue, _removeAttribute, _splitName, _stripNumericSuffix, addChangeListener, addDebugListener, attributeList, attributeList, deepContains, depthInHierarchy, description, description, event, executeChangeRequests, exportMoML, exportMoML, exportMoML, exportMoML, getAttribute, getAttributes, getChangeListeners, getClassName, getDerivedLevel, getDerivedList, getFullName, getModelErrorHandler, getName, getName, getSource, handleModelError, isDeferringChangeRequests, isOverridden, isPersistent, message, propagateValue, propagateValues, removeChangeListener, removeDebugListener, requestChange, setClassName, setDeferringChangeRequests, setDerivedLevel, setModelErrorHandler, setPersistent, setSource, toplevel, toString, workspace
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface ptolemy.actor.Actor
getDirector, getExecutiveDirector, getFunctionDependency, getManager, inputPortList, newReceiver, outputPortList
 
Methods inherited from interface ptolemy.actor.Executable
iterate, prefire, preinitialize, stop, stopFire, terminate, wrapup
 
Methods inherited from interface ptolemy.kernel.util.Derivable
getDerivedLevel, getDerivedList, propagateValue
 
Methods inherited from interface ptolemy.kernel.util.Nameable
description, getFullName, getName, getName
 

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.

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.

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 Executable
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