Forum: GNU Radio Question on gr-trellis PS and PI matricies in FSM

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
93bcc40cd07916689fe7de8afde22af1?d=identicon&s=25 Tim Meehan (Guest)
on 2007-02-01 14:53
(Received via mailing list)
Hello all,

I was trying to use the Viterbi decoder in gr-trellis for maximum
likelihood sequence detection of a bit-stuffed data source.  Here the
FSM is the bit-stuffing operation.  A reference for this is

Meehan, T.; Hicks, J.; Kragh, F., "Maximum Likelihood Sequence
Detection of a Bit-stuffed Data Source," Communications, 2006. ICC
'06. IEEE International Conference on , vol.4, no.pp.1514-1519, June
2006

For this application the number of branches entering a state is not
the same as the number leaving at a state.  The documentation for
gr-trellis states

"In the following we assume that for any state, the number of incoming
transitions is the same as the number of outgoing transitions, ie,
equal to I. All applications of interest have FSMs satisfying this
requirement."

Before I started digging in to modifying the code (or porting my
existing decoder to the gnuradio framework) I wanted to see if anyone
else was working to support different number of input branches to
output branches.

I think at a minimum the method "fsm::generate_PS_PI()" should check
to verify that the FSM description does in fact have the same number
of incoming branches and outing branches at each state.

If there is interest in making gr-trellis support this type of FSM I
can work on it, else I will probably just port my existing work over.

Please let me know what you think.


Tim
93bcc40cd07916689fe7de8afde22af1?d=identicon&s=25 Tim Meehan (Guest)
on 2007-02-01 16:32
(Received via mailing list)
Hello all,

I was trying to use the Viterbi decoder in gr-trellis for maximum
likelihood sequence detection of a bit-stuffed data source.  Here the
FSM is the bit-stuffing operation.  A reference for this is

Meehan, T.; Hicks, J.; Kragh, F., "Maximum Likelihood Sequence
Detection of a Bit-stuffed Data Source," Communications, 2006. ICC
'06. IEEE International Conference on , vol.4, no.pp.1514-1519, June
2006

For this application the number of branches entering a state is not
the same as the number leaving at a state.  The documentation for
gr-trellis states

"In the following we assume that for any state, the number of incoming
transitions is the same as the number of outgoing transitions, ie,
equal to I. All applications of interest have FSMs satisfying this
requirement."

Before I started digging in to modifying the code (or porting my
existing decoder to the gnuradio framework) I wanted to see if anyone
else was working to support different number of input branches to
output branches.

I think at a minimum the method "fsm::generate_PS_PI()" should check
to verify that the FSM description does in fact have the same number
of incoming branches and outing branches at each state.

If there is interest in making gr-trellis support this type of FSM I
can work on it, else I will probably just port my existing work over.

Please let me know what you think.

P.S.  Forgive me if I this shows up twice.  I did not see my original
post and have changed my address with the list.

Tim
C369ebbe1655201988e376af57460f23?d=identicon&s=25 Achilleas Anastasopoulos (Guest)
on 2007-09-25 23:05
(Received via mailing list)
Dear Tim,

it was indeed a minor modification that was required.
I made and it is working fine now.

It will take me some time to clean up the code
(as you can see the TM() method complains, but
the correction should be trivial there...)



If you want to start working on your project
just copy the files I attach
to the gr-trellis/src/lib directory
execute ./generat_all.py
and then execute make and make install from gr-trellis
directory.

I am also attaching a toy irregular FSM file.
put it in the directory
gnuradio-examples/python/channel-coding/fms_files.
Then run the modified test_tcm.py and run it.
It works.

Please let me know if you catch any bugs that I missed...

Achilleas
















============================
Dear Tim,,

indeed the current implementation supports only this kind of "regular"
trellises.
I believe the intruduction of non-regular trellises (ie, ones having
exactly I outgoing edges from each state, but different incoming edges
to each state) is a good idea.

They way I think about it, I have to substitute the PS (and PI)
internally generated matrix which is now of size SxI with a vector of
size S where each element is a  vector of size equal to the number of
incoming edges in the particular state. Then a couple of minor
modifications to the VA, and it is done...

I am not sure how familiar you are with the code I developed in
gr-trellis, but I am willing to help you make the modifications.

Best
Achilleas
745d8202ef5a58c1058d0e5395a78f9c?d=identicon&s=25 Eric Blossom (Guest)
on 2007-09-25 23:08
(Received via mailing list)
On Thu, Feb 01, 2007 at 12:51:03PM -0500, Achilleas Anastasopoulos
wrote:
> size S where each element is a  vector of size equal to the number of
> incoming edges in the particular state. Then a couple of minor
> modifications to the VA, and it is done...
>
> I am not sure how familiar you are with the code I developed in
> gr-trellis, but I am willing to help you make the modifications.
>
> Best
> Achilleas

Thanks to both of you!
Looking forward to having more great stuff in GNU Radio.

Eric
C369ebbe1655201988e376af57460f23?d=identicon&s=25 Achilleas Anastasopoulos (Guest)
on 2007-09-25 23:10
(Received via mailing list)
Dear Tim,,

indeed the current implementation supports only this kind of "regular"
trellises.
I believe the intruduction of non-regular trellises (ie, ones having
exactly I outgoing edges from each state, but different incoming edges
to each state) is a good idea.

They way I think about it, I have to substitute the PS (and PI)
internally generated matrix which is now of size SxI with a vector of
size S where each element is a  vector of size equal to the number of
incoming edges in the particular state. Then a couple of minor
modifications to the VA, and it is done...

I am not sure how familiar you are with the code I developed in
gr-trellis, but I am willing to help you make the modifications.

Best
Achilleas
This topic is locked and can not be replied to.