Method and apparatus for implementing a time varying trellis

A maximum likelihood detection trellis structure, comprising:

• a trellis onto which 2N binary states have been mapped at each discrete time of a sequence of times, said N≧2;
• 2 branches to each of the 2N binary states at time Ti+1 from a closest previous time Ti for a total of 2N+1 such branches between Ti and Ti+1, said i≧N or i≧1;
• a first illegal branch of said 2 branches to a state S1 at time Ti+1;
• and
• another branch of said 2 branches to the state S1, said another branch selected from the group consisting of a second illegal branch and a paralegal branch.

An Illegal Branch Exclusion method for calculating a state metric ST_Z of an output state Z given input states X and Y, the method comprising:

• providing a state metric ST_X of the input state X and a branch metric BR_X_Z of a branch X→Z from the input state X to the output state Z;
• providing a state metric ST_Y of the input state Y and a branch metric BR_Y_Z of a branch Y→Z from the input state Y to the output state Z, said X→Z and Y→Z are both legal or one of said X→Z and Y→Z is illegal and the other of said X→Z and Y→Z is paralegal;
• defining A=ST_X+BR_X_Z, B=ST_Y+BR_Y_Z, and a relational condition selected from the group consisting of A>B and A<B;
• and
• calculating ST_Z such that:
• if X→Z and Y→Z are both legal then said calculating ST_Z is according to ST_Z=B if the relational condition is true or ST_Z=A if the relational condition is false, if X→Z is illegal then said calculating ST_Z is according to ST_Z=B, if Y→Z is illegal then said calculating ST_Z is according to ST_Z=A.

A Large State Metric Value method for calculating a state metric ST_Z of an output state Z given input states X and Y, the method comprising:

• providing a state metric ST_X of the input state X and a branch metric BR_X_Z of a branch X→Z from the input state X to the output state Z;
• providing a state metric ST_Y of the input state Y and a branch metric BR_Y_Z of a branch Y→Z from the input state Y to the output state Z, said X→Z and Y→Z are both legal or said X→Z and Y→Z are both illegal;
• defining A=ST_X+BR_X_Z, B=ST_Y+BR_Y_Z, and a relational condition selected from the group consisting of A>B and A<B;
• and
• calculating ST_Z such that:
• if X→Z and Y→Z are both legal then said calculating ST_Z is according to ST_Z=B if the relational condition is true or ST_Z=A if the relational condition is false, if X→Z and Y→Z are both illegal then said calculating ST_Z is according to ST_Z=LSMV, said LSMV being positive and sufficiently large if the relational condition is A>B or said LSMV being negative and sufficiently large if the relational condition is A<B.

A TVT_M2M2 apparatus configured to calculate a state metric ST_Z of an output state Z given input states X and Y, comprising:

• an adder configured to compute A and B, said A=ST_X+BR_X_Z, said ST_X being a state metric of the input state X, said BR_X_Z being a branch metric of a branch X→Z from the input state X to the output state Z, said B=ST_Y+BR_Y_Z, said ST_Y being a state metric of the input state Y, said BR_Y_Z being a branch metric of a branch Y→Z from the input state Y to the output state Z, said X→Z and Y→Z are both legal or one of said X→Z and Y→Z is illegal and the other of said X→Z and Y→Z is paralegal;
• a comparator configured to receive A and B from said adder, said comparator configured to compare A and B to ascertain whether a relational condition is true, said comparator configured to generate a comparator output of 1 if the relational condition is true or to generate the comparator output of 0 if the relational condition is false, said relational condition being selected from the group consisting of A>B and A<B;
• a first multiplexor (MUX1) having input ports D0 and D1 and select input SEL1, said D0 configured to receive the comparator output, said D1 configured to receive 0 if said Y→Z is illegal, said D1 configured to receive 1 if said X→Z illegal, said SEL1 configured to be set to 0 if said X→Z and Y→Z are both legal, said SEL1 configured to be set to 1 if one of said X→Z and Y→Z is illegal and the other of said X→Z and Y→Z is paralegal, if SEL1=0 said MUX1 configured to select D0, if SEL1=1 said MUX1 configured to select D1, said MUX1 configured to generate a MUX1 output of what the MUX1 has selected;
• and
• a second multiplexor (MUX2) having input ports E0 and E1 and select input SEL2, said E0 configured to receive A from the adder, said E1 configured to receive B from the adder, set SEL2 configured to receive the MUX1 output, if SEL2=0 then said MUX2 configured to select E0, if SEL2=1 then said MUX2 configured to select E1, said MUX2 configured to generate a MUX2 output of what the MUX2 has selected, said ST_Z=said MUX2 output.

A TVT_M3 apparatus configured to calculate a state metric ST_Z of an output state Z given input states X and Y, comprising:

• an adder configured to compute A and B, said A=ST_X+BR_X_Z, said ST_X being a state metric of the input state X, said BR_X→Z being a branch metric of a branch X→Z from the input state X to the output state Z, said B=ST_Y+BR_Y_Z, said ST_Y being a state metric of the input state Y, said BR_Y_Z being a branch metric of a branch Y→Z from the input state Y to the output state Z, said X→Z and Y→Z both legal or said X→Z and Y→Z both illegal;
• a comparator configured to receive A and B from said adder, said comparator configured to compare A and B to ascertain whether a relational condition is true, said comparator configured to generate a comparator output of 1 if the relational condition is true or the comparator output of 0 if the relational condition is not true, said relational condition being selected from the group consisting of A>B and A<B;
• a multiplexor (MUX) having input ports D0, D1, and D2 and select inputs SEL1 and SEL2, said D0 configured to receive to receive A from the adder, said Dl configured to receive B from the adder;
• said D2 configured to receive to receive a Large State Metric Value (LSMV), said LSMV being positive and sufficiently large if said relational condition is A>B or said LSMV being negative and sufficiently large if said relational condition is A<B, said SEL1 configured to be set to 0 if said X→Z and Y→Z are both legal, said SEL1 configured to be set to 1 if said X→Z and Y→Z both illegal, said SEL2 configured to receive the comparator output from the comparator, if SEL1=0 then said MUX configured to select D0 if SEL2=0 or to select D1 if SEL2=1, if SEL1=1 then said MUX configured to select D2, said MUX generating a MUX output of what the MUX has selected, said ST_Z=said MUX output.