2013-12-27 05:42:53 +00:00
|
|
|
// ----------------------------------------------------------------------------
|
2013-12-30 04:59:42 +00:00
|
|
|
// trelis.c -- bayesian morse code decoder
|
2013-12-27 05:42:53 +00:00
|
|
|
//
|
|
|
|
// Copyright (C) 2012-2014
|
|
|
|
// (C) Mauri Niininen, AG1LE
|
|
|
|
//
|
2013-12-30 04:59:42 +00:00
|
|
|
// This file is part of Bayesian Morse code decoder
|
2013-12-27 05:42:53 +00:00
|
|
|
|
2013-12-30 04:59:42 +00:00
|
|
|
// bmorse is free software: you can redistribute it and/or modify
|
2013-12-27 05:42:53 +00:00
|
|
|
// it under the terms of the GNU General Public License as published by
|
|
|
|
// the Free Software Foundation, either version 3 of the License, or
|
|
|
|
// (at your option) any later version.
|
|
|
|
//
|
2013-12-30 04:59:42 +00:00
|
|
|
// bmorse is distributed in the hope that it will be useful,
|
2013-12-27 05:42:53 +00:00
|
|
|
// but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
|
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
|
// GNU General Public License for more details.
|
|
|
|
//
|
|
|
|
// You should have received a copy of the GNU General Public License
|
2013-12-30 04:59:42 +00:00
|
|
|
// along with bmorse. If not, see <http://www.gnu.org/licenses/>.
|
2013-12-27 05:42:53 +00:00
|
|
|
// ----------------------------------------------------------------------------
|
|
|
|
|
2013-09-02 17:07:28 +00:00
|
|
|
#include <stdio.h>
|
2013-12-30 04:59:42 +00:00
|
|
|
#include "bmorse.h"
|
2013-09-02 17:07:28 +00:00
|
|
|
|
|
|
|
//#define DEBUG 1
|
2013-09-02 02:12:51 +00:00
|
|
|
|
|
|
|
|
2014-07-19 22:00:18 +00:00
|
|
|
int morse::trelis_(long int *isave, long int *pathsv, long int *lambda, long int *imax, long int *ipmax, char *buf)
|
2013-09-02 02:12:51 +00:00
|
|
|
{
|
|
|
|
|
|
|
|
|
2014-07-19 22:00:18 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* Local variables */
|
2014-06-22 19:30:00 +00:00
|
|
|
int i, k, ip, ieq, ltr, ndel, retstat;
|
2013-09-26 01:25:34 +00:00
|
|
|
static int isavg, init=0;
|
2014-07-19 22:00:18 +00:00
|
|
|
static float xsavg, xmmax, xnmax;
|
2014-06-22 19:30:00 +00:00
|
|
|
int ndlavg;
|
2014-07-19 22:00:18 +00:00
|
|
|
static float xdlavg;
|
2013-09-02 02:12:51 +00:00
|
|
|
|
|
|
|
/* THIS SUBROUTINE STORES THE SAVED NODES AT EACH */
|
|
|
|
/* STAGE AND FORMS THE TREE OF SAVED PATHS LINKING */
|
|
|
|
/* THE NODES. DECODING IS ACCOMPLISHED BY FINDING */
|
|
|
|
/* THE CONVERGENT PATH IF IT OCCURS WITHIN A MAXIMUM */
|
|
|
|
/* DELAY SET BY THE PARAMETER NDELAY. IF CONVERGENCE */
|
|
|
|
/* TO A SINGLE PATH DOES NOT OCCURS, THEN DECODING IS */
|
|
|
|
/* DONE BY READING THE LETTER ON THE PATH WITH HIGHEST */
|
|
|
|
/* PROBABILITY */
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* Parameter adjustments */
|
|
|
|
--lambda;
|
|
|
|
--pathsv;
|
|
|
|
|
2014-01-20 04:12:52 +00:00
|
|
|
/* initialize variables*/
|
2013-09-26 01:25:34 +00:00
|
|
|
if (init ==0) {
|
|
|
|
init = 1;
|
2014-01-20 04:12:52 +00:00
|
|
|
for (i=0; i< NDELAY; i++)
|
|
|
|
ltrsv[i] = 0;
|
2014-05-25 05:37:09 +00:00
|
|
|
for (int row =0; row < PATHS; row++) {
|
2014-01-20 04:12:52 +00:00
|
|
|
ipnod[row] = 1;
|
|
|
|
for (int col =0; col < NDELAY; col++){
|
|
|
|
lmdsav[row][col] = 0;
|
|
|
|
pthtrl[row][col] = 0;
|
|
|
|
}
|
2013-09-26 01:25:34 +00:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* KEEP AVERAGE OF ISAVE, NDEL FOR DATA ANALYSIS: */
|
2014-01-02 02:58:00 +00:00
|
|
|
|
2013-09-08 04:17:35 +00:00
|
|
|
retstat = 1;
|
2013-09-02 02:12:51 +00:00
|
|
|
++ncall;
|
2014-01-02 02:58:00 +00:00
|
|
|
if (iend == 1) {
|
2013-09-26 01:25:34 +00:00
|
|
|
isavg = xsavg;
|
|
|
|
ndlavg = xdlavg;
|
2014-01-02 02:58:00 +00:00
|
|
|
iend = 0;
|
2013-09-26 01:25:34 +00:00
|
|
|
printf("\nAVG # OF PATHS SAVED:%4.2f,AVG DECODE DELAY:%4.2f)", xsavg, xdlavg);
|
|
|
|
printf("\nPERCENT OF TIME PATHS = 25: %3.2f, PERCENT OF TIME DELAY = 200: %3.2f", xmmax, xnmax);
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
|
|
|
xsavg = (xsavg * (ncall - 1) + *isave) / ncall;
|
|
|
|
xdlavg = (xdlavg * (ncall - 1) + ndel) / ncall;
|
2013-09-26 01:25:34 +00:00
|
|
|
if (ndel == ndelay) {
|
|
|
|
++nmax;
|
2014-07-19 22:00:18 +00:00
|
|
|
xnmax = (float) nmax;
|
2013-09-26 01:25:34 +00:00
|
|
|
xnmax /= ncall;
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2014-05-25 05:37:09 +00:00
|
|
|
if (*isave == PATHS) {
|
2013-09-26 01:25:34 +00:00
|
|
|
++mmax;
|
2014-07-19 22:00:18 +00:00
|
|
|
xmmax = (float) mmax;
|
2013-09-26 01:25:34 +00:00
|
|
|
xmmax /= ncall;
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* STORE PATHSV AND CORRESPONDING LAMBDA IN THE */
|
|
|
|
/* TRELLIS USING A CIRCULAR BUFFER OF LENGTH NDELAY : */
|
|
|
|
++n;
|
|
|
|
if (n == ndelay + 1) {
|
2013-09-26 01:25:34 +00:00
|
|
|
n = 1;
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2014-06-08 18:55:45 +00:00
|
|
|
|
|
|
|
for (i = 1; i <= *isave; ++i) {
|
2014-06-22 19:30:00 +00:00
|
|
|
pthtrl[i-1][n-1] = pathsv[i];
|
2014-07-19 22:00:18 +00:00
|
|
|
lmdsav[i-1][n-1] = (long int)lambda[i];
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* PERFORM DYNAMIC PROGRAM ROUTINE TO FIND CONVERGENT PATH: */
|
|
|
|
k = 0;
|
2014-06-08 18:55:45 +00:00
|
|
|
for (i = 1; i <= *isave; ++i) {
|
2013-09-26 01:25:34 +00:00
|
|
|
ipnod[i - 1] = i;
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
|
|
|
L190:
|
|
|
|
++k;
|
|
|
|
if (k == ndelay) {
|
2013-09-26 01:25:34 +00:00
|
|
|
goto L700;
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* IF IP EQUALS INDEX OF HIGHEST PROBABILITY NODE, STORE NODE TO IPMAX */
|
2014-06-08 18:55:45 +00:00
|
|
|
for (ip = 1; ip <= *isave; ++ip) {
|
2013-09-26 01:25:34 +00:00
|
|
|
i = n - k + 1;
|
|
|
|
if (i <= 0) {
|
|
|
|
i = ndelay + i;
|
|
|
|
}
|
2014-01-20 04:12:52 +00:00
|
|
|
ipnod[ip - 1] = pthtrl[ipnod[ip - 1]-1][i-1];
|
2013-09-26 01:25:34 +00:00
|
|
|
if (ip == *imax) {
|
|
|
|
*ipmax = ipnod[ip - 1];
|
|
|
|
}
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* IF ALL NODES ARE EQUAL,THEN PATHS CONVERGE: */
|
2014-06-08 18:55:45 +00:00
|
|
|
|
|
|
|
for (ieq = 2; ieq <= *isave; ++ieq) {
|
2013-09-26 01:25:34 +00:00
|
|
|
if (ipnod[0] != ipnod[ieq - 1]) {
|
|
|
|
goto L190;
|
|
|
|
}
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* PATHS CONVERGE; SET NDEL: */
|
|
|
|
ndel = k + 1;
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* IF POINT OF CONVERGENCE IS SAME AS IT WAS ON */
|
|
|
|
/* LAST CALL, THEN NO NEED TO RE-DECODE SAME NODE: */
|
|
|
|
if (ndel == ndelst + 1) {
|
2013-09-26 01:25:34 +00:00
|
|
|
goto L800;
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
|
|
|
/* IF POINT OF CONVERGENCE OCCURS AT SAME DELAY AS LAST CALL, THEN TRANSLATE: */
|
|
|
|
if (ndel != ndelst) {
|
2013-09-26 01:25:34 +00:00
|
|
|
goto L350;
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2013-09-02 17:07:28 +00:00
|
|
|
i = n - ndel + 1;
|
|
|
|
if (i <= 0) {
|
2013-09-26 01:25:34 +00:00
|
|
|
i = ndelay + i;
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2014-01-20 04:12:52 +00:00
|
|
|
ltr = lmdsav[ipnod[0]-1][i-1];
|
2014-07-19 22:00:18 +00:00
|
|
|
retstat = transl_(ltr,buf);
|
2013-09-02 02:12:51 +00:00
|
|
|
goto L800;
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* OTHERWISE,POINT OF CONVERGENCE HAS OCCURED */
|
|
|
|
/* EARLIER ON THIS CALL, SO NEED TO TRANSLATE */
|
|
|
|
/* EVERYTHING ON THE CONVERGENT PATH FROM */
|
|
|
|
/* PREVIOUS POINT OF CONVERGENCE TO THIS POINT: */
|
|
|
|
L350:
|
|
|
|
kd = 0;
|
|
|
|
ip = ipnod[0];
|
2014-06-08 18:55:45 +00:00
|
|
|
for (k = ndel; k <= ndelst; ++k) {
|
2013-09-26 01:25:34 +00:00
|
|
|
++kd;
|
|
|
|
i = n - k + 1;
|
|
|
|
if (i <= 0) {
|
|
|
|
i = ndelay + i;
|
|
|
|
}
|
2014-01-20 04:12:52 +00:00
|
|
|
ltrsv[kd - 1] = lmdsav[ip-1][i-1];
|
|
|
|
ip = pthtrl[ip-1][i-1];
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* REVERSE ORDER OF DECODED LETTERS, SINCE THEY */
|
|
|
|
/* WERE OBTAINED FROM THE TRELLIS IN REVERSE; */
|
|
|
|
/* TRANSLATE EACH: */
|
2014-06-08 18:55:45 +00:00
|
|
|
|
|
|
|
for (i = 1; i <= kd; ++i) {
|
2013-09-26 01:25:34 +00:00
|
|
|
ltr = ltrsv[kd - i];
|
2014-07-19 22:00:18 +00:00
|
|
|
retstat = transl_(ltr,buf);
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
|
|
|
goto L800;
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
L700:
|
|
|
|
/* PATHS HAVE NOT CONVERGED AT MAXIMUM ALLOWABLE */
|
|
|
|
/* DELAY, SO TRANSLATE WHAT IS ON HIGHEST */
|
|
|
|
/* PROBABILITY PATH: */
|
|
|
|
ndel = ndelay;
|
2013-09-02 17:07:28 +00:00
|
|
|
i = n - ndelay + 1;
|
|
|
|
if (i <= 0) {
|
2013-09-26 01:25:34 +00:00
|
|
|
i = ndelay + i;
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2014-01-20 04:12:52 +00:00
|
|
|
ltr = lmdsav[*ipmax-1][i -1];
|
2014-07-19 22:00:18 +00:00
|
|
|
retstat = transl_(ltr,buf);
|
2014-06-22 19:30:00 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
/* PRUNE AWAY NODES WHICH ARE NOT ON THIS PATH: */
|
2014-06-08 18:55:45 +00:00
|
|
|
for (k = 1; k <= *isave; ++k) {
|
2013-09-26 01:25:34 +00:00
|
|
|
if (ipnod[k - 1] != *ipmax) {
|
|
|
|
lambda[k] = 0;
|
|
|
|
}
|
2013-09-02 02:12:51 +00:00
|
|
|
}
|
2013-09-26 01:25:34 +00:00
|
|
|
|
2013-09-02 02:12:51 +00:00
|
|
|
L800:
|
|
|
|
ndelst = ndel;
|
2013-09-08 04:17:35 +00:00
|
|
|
return retstat;
|
2013-09-02 02:12:51 +00:00
|
|
|
} /* trelis_ */
|
|
|
|
|