std::vector<int> d_OS;
std::vector<int> d_PS;
std::vector<int> d_PI;
+ std::vector<int> d_TMi;
+ std::vector<int> d_TMl;
+ void generate_PS_PI ();
+ void generate_TM ();
+ bool find_es(int es);
public:
fsm();
fsm(const fsm &FSM);
- fsm(const int I, const int S, const int O, const std::vector<int> &NS, const std::vector<int> &OS);
+ fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> &OS);
fsm(const char *name);
- fsm(const int mod_size, const int ch_length);
+ fsm(int k, int n, const std::vector<int> &G);
+ fsm(int mod_size, int ch_length);
int I () const { return d_I; }
int S () const { return d_S; }
int O () const { return d_O; }
const std::vector<int> & OS () const { return d_OS; }
const std::vector<int> & PS () const { return d_PS; }
const std::vector<int> & PI () const { return d_PI; }
+ const std::vector<int> & TMi () const { return d_TMi; }
+ const std::vector<int> & TMl () const { return d_TMl; }
};
</programlisting>
</para>
</listitem>
+
+<listitem>
+<para>
+The third way is specific to FSMs representing binary (n,k) conolutional codes. These FSMs are specified by the number of input bits k, the number of output bits n, and the generator matrix, which is a k x n matrix of integers
+G = [g<subscript>i,j</subscript>]<subscript>i=1:k, j=1:n</subscript>, given as an one-dimensional STL vector.
+Each integer g<subscript>i,j</subscript> is the decimal representation of the
+polynomial g<subscript>i,j</subscript>(D) (e.g., g<subscript>i,j</subscript>= 6 = 110<subscript>2</subscript> is interpreted as g<subscript>i,j</subscript>(D)=1+D) describing the connections from the sequence x<subscript>i</subscript> to
+y<subscript>j</subscript> (e.g., in the above example y<subscript>j</subscript>(k) = x<subscript>i</subscript>(k) + x<subscript>i</subscript>(k-1)).
+</para>
+<programlisting>
+ fsm(int k, int n, const std::vector<int> &G);
+</programlisting>
+</listitem>
+
+
<listitem>
-<para>The third way is specific to FSMs resulting from shift registers, and the output symbol being the entire transition (ie, current_state and current_input). These FSMs are usefull when describibg ISI channels. In particular the state is comprised of the.....
+<para>
+The fourth way is specific to FSMs resulting from shift registers, and the output symbol being the entire transition (ie, current_state and current_input). These FSMs are usefull when describibg ISI channels. In particular the state is comprised of the input symbols x(k-1), x(k-2),...,x(k-L), where L = ch_length-1 and each x(i) belongs to an alphabet of size mod_size. The output is taken to be x(k), x(k-1), x(k-2),...,x(k-L) (in decimal format)
</para>
<programlisting>
fsm(const int mod_size, const int ch_length);
<para>
-Finally, as can be seen from the above description, there are
+As can be seen from the above description, there are
two more variables included in the FSM class implementation,
the PS and the PI matrices. These are computed internally
when an FSM is instantiated and their meaning is as follows.
</para>
+<para>
+Finally, there are
+two more variables included in the FSM class implementation,
+the TMl and the TMi matrices. These are both S x S matrices (represented as STL vectors) computed internally
+when an FSM is instantiated and their meaning is as follows.
+TMl(i,j) is the minimum number of trellis steps required to go from state i to state j.
+Similarly, TMi(i,j) is the initial input required to get you from state i to state j in the minimum number of steps. As an example, if TMl(1,4)=2, it means that you need 2 steps in the trellis to get from state 1 to state 4. Further,
+if TMi(1,4)=0 it means that the first such step will be followed if when at state 1 the input is 0. Furthermore, suppose that NS(1,0)=2. Then, TMl(2,4) should be 1 (ie, one more step is needed when starting from state 2 and having state 4 as the final destination). Finally, TMi(2,4) will give us the second input required to complete the path from 1 to 4.
+These matrices are useful when we want to implement an encoder with proper state termination. For instance, based on these matrices we can evaluate how many
+additional input symbols (and which particular inputs) are required to be appended at the end of an input sequence so that the final state is always 0.
+
+</para>
+
+
</sect1>
+<!--=====================================================-->
+<sect1 id="blocks"><title>Blocks Using the FSM structure</title>
+
+<para>
+In this section we give a brief description of the basic blocks implemented that make use of the previously described FSM structure.
+</para>
+
+
+<!-- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -->
+<sect2 id="encoder"><title>Trellis Encoder</title>
+<para>
+The trellis.encoder_XX(FSM, ST) block instantiates an FSM encoder corresponding to the fsm FSM and having initial state ST. The input and output is a sequence of bytes, shorts or integers.
+</para>
+</sect2>
+
+<!-- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -->
+<sect2 id="decoder"><title>Viterbi Decoder</title>
+<para>
+The trellis.viterbi_X(FSM, K, S0, SK) block instantiates a Viterbi decoder
+for a sequence of K trellis steps generated by the given FSM and with initial and final states set to S0 and SK, respectively (S0 and/or SK are set to -1
+if the corresponding states are not fixed/known at the receiver side).
+The output of this block is a sequence of K bytes, shorts or integers representing the estimated input (i.e., uncoded) sequence.
+The input is a sequence of K x FSM.O( ) floats, where the k x K + i
+float represents the cost associated with the k-th
+step in the trellis and the i-th FSM output.
+Observe that these inputs are generated externally and thus the Viterbi block is not informed of their meaning (they can be genarated as soft or hard inputs, etc); the only requirement is that they represent additive costs.
+</para>
+</sect2>
+
+<!-- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -->
+<sect2 id="metrics"><title>Metrics Calculator</title>
+<para>
+The trellis.metrics_X(O,D,TABLE,TYPE) block is responsible for
+transforming the channel output to the stream of metrics appropriate as
+inputs to the Viterbi block described above. For each D input bytes/shorts/integers/floats/complexes it produces O output floats
+
+</para>
+
+<para>
+
+The parameter TYPE dictates how these metrics are generated:
+
+<itemizedlist>
+<listitem><para>
+TRELLIS_EUCLIDEAN: for each D-dimensional vector
+r<subscript>k</subscript>=
+(r<subscript>k,1</subscript>,r<subscript>k,2</subscript>,...,r<subscript>k,D</subscript>)
+evaluates
+</para>
+<para>
+||r<subscript>k</subscript>-c<subscript>i</subscript>||<superscript>2</superscript> = sum<subscript>j=1</subscript><superscript>D</superscript> |r<subscript>k,j</subscript>-c<subscript>i,j</subscript>|<superscript>2</superscript>
+</para>
+<para>
+for each of the O hypothesized ouput
+symbols c<subscript>i</subscript> = (c<subscript>i,1</subscript>,c<subscript>i,2</subscript>,...,c<subscript>i,D</subscript>) defined in the vector TABLE,
+where TABLE[i * D + j] = c<subscript>i,j</subscript>.
+</para></listitem>
+
+
+<listitem><para>
+TRELLIS_HARD_SYMBOL: for each D-dimensional vector
+r<subscript>k</subscript>=
+(r<subscript>k,1</subscript>,r<subscript>k,2</subscript>,...,r<subscript>k,D</subscript>)
+evaluates
+</para>
+<para>
+i<subscript>0</subscript>= argmax<subscript>i</subscript> ||r<subscript>k</subscript>-c<subscript>i</subscript>||<superscript>2</superscript> =
+argmax<subscript>i</subscript> sum<subscript>j=1</subscript><superscript>D</superscript> |r<subscript>k,j</subscript>-c<subscript>i,j</subscript>|<superscript>2</superscript>
+</para>
+<para>
+and outputs a sequence of O floats of the form (0,...,0,1,0,...,0), where the
+i<subscript>0</subscript> position is set to 1. This corresponds to generating hard inputs (based on the symbol-wise Hamming distance) to the Viterbi algorithm.
+</para></listitem>
+
+
+<listitem><para>
+TRELLIS_HARD_BIT (not yet implemented): for each D-dimensional vector
+r<subscript>k</subscript>=
+(r<subscript>k,1</subscript>,r<subscript>k,2</subscript>,...,r<subscript>k,D</subscript>)
+evaluates
+</para>
+<para>
+i<subscript>0</subscript>= argmax<subscript>i</subscript> ||r<subscript>k</subscript>-c<subscript>i</subscript>||<superscript>2</superscript> =
+argmax<subscript>i</subscript> sum<subscript>j=1</subscript><superscript>D</superscript> (r<subscript>k,j</subscript>-c<subscript>i,j</subscript>)<superscript>2</superscript>
+</para>
+<para>
+and outputs a sequence of O floats of the form (d<subscript>1</subscript>,d<subscript>2</subscript>,...,d<subscript>O</subscript>), where the
+d<subscript>i</subscript> is the bitwise Hamming distance between i and i<subscript>0</subscript>. This corresponds to generating hard inputs (based on the bit-wise Hamming distance) to the Viterbi algorithm.
+</para></listitem>
+
+
+</itemizedlist>
+
+
+</para>
+</sect2>
+
+
+
+
+<!-- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -->
+<sect2 id="viterbi_combined"><title>Combined Metrics Calculator and Viterbi Decoder</title>
+<para>
+Although the separation of metric calculation and Viterbi algorithm blocks
+is consistent with our goal of providing general blocks that can be easily
+reused, this separation might result in large input/output buffer sizes
+betwen blocks. Indeed for an FSM with a large output alphabet, the
+output of the metric block/input of the Viterbi block is FSM.O( ) floats for
+each trellis step. Sometimes this results in buffer overflow even for
+moderate sequence lengths.
+To overcome this problem we provide a block that incorporates the metric calculation and Viterbi algorithm into a single GNU Radio block, namely
+trellis.viterbi_combined_X( FSM, K, S0, SK, D, TABLE, TYPE) where the arguments are exactly those used in the aforementioned two blocks.
+</para>
+</sect2>
+
+
+
+
+
+</sect1>
<!--=====================================================-->
The FSM is first intantiated in "main" by
</para>
<programlisting>
- 62 f=trellis.fsm(fname) # get the FSM specification from a file (will hopefully be automated in the future...)
+ 62 f=trellis.fsm(fname) # get the FSM specification from a file
</programlisting>
<para>
-The FSM will produce K output symbols (remeber the FSM produces always one output symbol for each input symbol). Each of these symbols needs to be modulated. Since we are simulating the communication system, we need not simulate the actual waveforms. An M-ary, N-dimensional
-modulation is completely specified by a set of M, N-dimensional real vectors. In "fsm_utils.py" file we give a number of useful modulations with the following format: modulation = (N,constellation), where
-constellation=[c11,c12,...,c1N,c21,c22,...,c2N,...,cM1,cM2,...cMN].
+The FSM will produce K output symbols (remeber the FSM produces always one output symbol for each input symbol). Each of these symbols needs to be modulated. Since we are simulating the communication system, we need not simulate the actual waveforms. An M-ary, D-dimensional
+modulation is completely specified by a set of M, D-dimensional real vectors. In "fsm_utils.py" file we give a number of useful modulations with the following format: modulation = (D,constellation), where
+constellation=[c11,c12,...,c1D,c21,c22,...,c2D,...,cM1,cM2,...cMD].
The meaning of the above is that every constellation point c_i
-is an N-dimnsional vector c_i=(ci1,ci2,...,ciN)
+is an D-dimnsional vector c_i=(ci1,ci2,...,ciD)
For instance, 4-ary PAM is represented as
(1,[-3, -1, 1, 3]), while QPSK is represented as
(2,[1, 0, 0, 1, 0, -1, -1, 0]). In our example we choose QPSK modulation.
We now need to modulate the FSM output symbols.
The "chunks_to_symbols_sf" is essentially a memoryless mapper which
for each input symbol y_k
-outputs a sequence of N numbers ci1,ci2,...,ciN representing the
+outputs a sequence of D numbers ci1,ci2,...,ciD representing the
coordianates of the constellation symbol c_i with i=y_k.
</para>
<programlisting>
<para>
The channel is AWGN with appropriate noise variance.
-For each transmitted symbol c_k=(ck1,ck2,...,ckN) we receive a noisy version
-r_k=(rk1,rk2,...,rkN).
+For each transmitted symbol c_k=(ck1,ck2,...,ckD) we receive a noisy version
+r_k=(rk1,rk2,...,rkD).
</para>
<programlisting>
22 # CHANNEL
O such numbers (one for each possible output symbol y_k).
This is done
in "metrics_f". In particular, metrics_f is a memoryless device
-taking N inputs at a time and producing O outputs. The N inputs are
-rk1,rk2,...,rkN.
+taking D inputs at a time and producing O outputs. The D inputs are
+rk1,rk2,...,rkD.
The O outputs
-are the costs associated with observations rk1,rk2,...,rkN and
+are the costs associated with observations rk1,rk2,...,rkD and
hypothesized output symbols c_1,c_2,...,c_M. For instance,
if we choose to perform soft-input VA, we need to evaluate
the Euclidean distance between r_k and each of c_1,c_2,...,c_M,
<listitem>
<para>
-automate fsm generation from generator polynomials
-(feedforward or feedback form).
+automate fsm generation from rational functions
+(feedback form).
</para>
</listitem>
<listitem>
<para>
-Optimize the VA code.
+Optimize the VA code if possible.
</para>
</listitem>
<listitem>
<para>
-Provide implementation of soft-input soft-output (SISO) decoders for
-potential use in concatenated systems. Also a host of suboptimal
+A host of suboptimal
decoders, eg, sphere decoding, M- and T- algorithms, sequential decoding, etc.
can be implemented.
</para>
use the encoder, and SISO blocks and connect them
through GNU radio or we should implement turbo-decoding
as a single block (issues with buffering between blocks).
+So far the former has been implemented.
</para>
</listitem>
projects / debian / gnuradio / blobdiff