Hi, Given a state-space description of a digital filter, is it possible to find a transformation matrix T so that the resulting representation is not only 'minimal' (number of states), but also using the simplest structure/coefficients? There are various methods to convert a given state-space into a minimal-state. However, there are a ton of possible representations of 'minimal', and the difference in implementation might be huge. As an example, a simple series of differentiators would have coefficients +1/-1, and nothing else - trivial to implement. Now if starting from another state space description (most likely with more states), is there an algorithm that would get me to the differentiators? I can go back to the correct number of states, but never in the form of differentiators. Thanks
Minimum realization from a state-space description
Started by ●January 22, 2013
Reply by ●January 22, 20132013-01-22
On 1/22/13 4:31 PM, gretzteam wrote:> > Given a state-space description of a digital filter, is it possible to find > a transformation matrix T so that the resulting representation is not only > 'minimal' (number of states), but also using the simplest > structure/coefficients?direct form 2. i would be willing to bet on that. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●January 22, 20132013-01-22
On Tue, 22 Jan 2013 15:31:23 -0600, gretzteam wrote:> Hi, > Given a state-space description of a digital filter, is it possible to > find a transformation matrix T so that the resulting representation is > not only 'minimal' (number of states), but also using the simplest > structure/coefficients? > > There are various methods to convert a given state-space into a > minimal-state. However, there are a ton of possible representations of > 'minimal', and the difference in implementation might be huge. > > As an example, a simple series of differentiators would have > coefficients +1/-1, and nothing else - trivial to implement. Now if > starting from another state space description (most likely with more > states), is there an algorithm that would get me to the differentiators? > I can go back to the correct number of states, but never in the form of > differentiators. > > ThanksDefine "simplest". In a DSP, you've pretty much got one MAC available per clock tick no matter what you do -- so adding to the accumulator is no more expensive than multiplying by a non-zero number and adding to the accumulator. FPGA's these days seem to come with a plethora of excess of MAC blocks (but it's probably only an excess until you start using them up!). So, ditto. If you reduce the state transition matrix down to the point where it's just eigenvalues on the diagonal (or perhaps so that it's in Jordanian form, if they're coupled), then you'll have a "simple" diagonal matrix, albeit with complex numbers. Bulk the thing back up to all real coefficients, in Jordanian form, and you'll have no more than three numbers off of the diagonal populated. I went around the mulberry bush on this quite a bit at one point, implementing control rules (which involve lots of IIR filtering and almost no FIR), and decided that the best way to do it was to reduce the system description to a state-space, and do a matrix multiply to get [x_n] [ A | B ][x_n-1] [---] = [---+---][-----] [y_n] [ C | D ][ u_n ] On the parts that I did this with, I had one-cycle MACs with index updating, hardware looping, and all the other DSP-ish things that make FIR filters way fast -- in consequence the speed at which I could do a MAC with one zero coefficient allowed this to be the most efficient way to get 'er done -- and I didn't have to do much special with the system description. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Reply by ●January 22, 20132013-01-22
> >Define "simplest". > >In a DSP, you've pretty much got one MAC available per clock tick no >matter what you do -- so adding to the accumulator is no more expensive >than multiplying by a non-zero number and adding to the accumulator. > >FPGA's these days seem to come with a plethora of excess of MAC blocks >(but it's probably only an excess until you start using them up!). So, >ditto. >I understand it might be possible to implement whatever complicated coefficient, but I was wondering if techniques/algorithms existed that also take into account coefficient complexity. As an example: this ridiculous state-space system: (posted at the end for clarity), can be implemented like this: y = u1- (diff*(u2- 0.5*diff*(u3- ((1/3)*diff*u4) which is a cascade of differentiators with gains in between. I would not have seen this looking at the original system, and if you use ready-made algorithm to reduce/optimize the state-space, you do end up with a 3 state design, but nowhere near the simple and elegant solution. Thanks system: sys = a = x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x1 0 0 0 0 0 0 0 0 0 0 0 0 x2 0 0 0 0 0 0 0 0 0 0 0 0 x3 0 0 0 0 0 0 0 0 0 0 0 0 x4 0 0 0 0 0 0 0 0 0 0 0 0 x5 1 0 0 0 0 0 0 0 0 0 0 0 x6 0 1 0 0 0 0 0 0 0 0 0 0 x7 0 0 1 0 0 0 0 0 0 0 0 0 x8 0 0 0 1 0 0 0 0 0 0 0 0 x9 0 0 0 0 1 0 0 0 0 0 0 0 x10 0 0 0 0 0 1 0 0 0 0 0 0 x11 0 0 0 0 0 0 1 0 0 0 0 0 x12 0 0 0 0 0 0 0 1 0 0 0 0 b = u1 u2 u3 u4 x1 1 0 0 0 x2 0 1 0 0 x3 0 0 1 0 x4 0 0 0 1 x5 0 0 0 0 x6 0 0 0 0 x7 0 0 0 0 x8 0 0 0 0 x9 0 0 0 0 x10 0 0 0 0 x11 0 0 0 0 x12 0 0 0 0 c = x1 x2 x3 x4 x5 x6 x7 x8 x9 y1 -1 1 0 -2.776e-17 0.5 -1 0.5 0 -0.1667 x10 x11 x12 y1 0.5 -0.5 0.1667 d = u1 u2 u3 u4 y1 1 0 0 0
Reply by ●January 22, 20132013-01-22
gretzteam <34989@dsprelated> wrote: (snip)> I understand it might be possible to implement whatever complicated > coefficient, but I was wondering if techniques/algorithms existed that also > take into account coefficient complexity.Depending on what you mean by complexity, there is the ICT, Integer Cosine Transform. http://ipnpr.jpl.nasa.gov/progress_report/42-105/105F.PDF http://ipnpr.jpl.nasa.gov/progress_report/42-115/115j.pdf Similar to the DCT (or FCT), it is designed for the case when the forward transform needs to be as fast as possible on a processor with no multiply instruction (such as the CDP1802). The inverse transform may be much slower. But there are many kinds of simplifications one might be interested in, each with its own algorithm. -- glen
Reply by ●January 22, 20132013-01-22
On Tue, 22 Jan 2013 17:39:01 -0600, gretzteam wrote:>>Define "simplest". >> >>In a DSP, you've pretty much got one MAC available per clock tick no >>matter what you do -- so adding to the accumulator is no more expensive >>than multiplying by a non-zero number and adding to the accumulator. >> >>FPGA's these days seem to come with a plethora of excess of MAC blocks >>(but it's probably only an excess until you start using them up!). So, >>ditto. >> >> > I understand it might be possible to implement whatever complicated > coefficient, but I was wondering if techniques/algorithms existed that > also take into account coefficient complexity. > > As an example: > > this ridiculous state-space system: > (posted at the end for clarity), > > can be implemented like this: > > y = u1- (diff*(u2- 0.5*diff*(u3- ((1/3)*diff*u4) which is a cascade of > differentiators with gains in between. I would not have seen this > looking at the original system, and if you use ready-made algorithm to > reduce/optimize the state-space, you do end up with a 3 state design, > but nowhere near the simple and elegant solution. > > Thanks > > system: > > sys = > > a = > x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 > x1 0 0 0 0 0 0 0 0 0 0 0 0 x2 > 0 0 0 0 0 0 0 0 0 0 0 0 x3 0 > 0 0 0 0 0 0 0 0 0 0 0 x4 0 0 > 0 0 0 0 0 0 0 0 0 0 x5 1 0 0 > 0 0 0 0 0 0 0 0 0 x6 0 1 0 0 > 0 0 0 0 0 0 0 0 x7 0 0 1 0 0 > 0 0 0 0 0 0 0 x8 0 0 0 1 0 0 > 0 0 0 0 0 0 x9 0 0 0 0 1 0 0 > 0 0 0 0 0 x10 0 0 0 0 0 1 0 0 > 0 0 0 0 x11 0 0 0 0 0 0 1 0 0 > 0 0 0 x12 0 0 0 0 0 0 0 1 0 0 > 0 0 > > b = > u1 u2 u3 u4 > x1 1 0 0 0 > x2 0 1 0 0 > x3 0 0 1 0 > x4 0 0 0 1 > x5 0 0 0 0 > x6 0 0 0 0 > x7 0 0 0 0 > x8 0 0 0 0 > x9 0 0 0 0 > x10 0 0 0 0 > x11 0 0 0 0 > x12 0 0 0 0 > > c = > x1 x2 x3 x4 x5 > x6 x7 x8 x9 > y1 -1 1 0 -2.776e-17 0.5 > -1 0.5 0 -0.1667 > > x10 x11 x12 > y1 0.5 -0.5 0.1667 > > d = > u1 u2 u3 u4 > y1 1 0 0 0Your system has nine unobservable states. First delve into the control systems literature to separate out the observable sub-system from the unobservable one, then consider my suggestion about converting the observable part to Jordanian form. -- My liberal friends think I'm a conservative kook. My conservative friends think I'm a liberal kook. Why am I not happy that they have found common ground? Tim Wescott, Communications, Control, Circuits & Software http://www.wescottdesign.com
Reply by ●January 23, 20132013-01-23
>Your system has nine unobservable states. First delve into the control >systems literature to separate out the observable sub-system from the >unobservable one, then consider my suggestion about converting the >observable part to Jordanian form. > >--Yes - hence why I was looking for an automatic way to simplify it. I gave this one as a *dumb* example since I happen to know the simplest implementation. Basically, I wonder if the problem of finding a transformation matrix T in order to *explore* the tradeoffs between the number of states, number of coefficients, coefficient complexity... I said *explore* since as you all said, optimal highly depends on the platform on which this will run, along with design criteria.
Reply by ●January 23, 20132013-01-23
On Wed, 23 Jan 2013 09:26:05 -0600, gretzteam wrote:>>Your system has nine unobservable states. First delve into the control >>systems literature to separate out the observable sub-system from the >>unobservable one, then consider my suggestion about converting the >>observable part to Jordanian form. >> >>-- > > > Yes - hence why I was looking for an automatic way to simplify it. I > gave this one as a *dumb* example since I happen to know the simplest > implementation. > > Basically, I wonder if the problem of finding a transformation matrix T > in order to *explore* the tradeoffs between the number of states, number > of coefficients, coefficient complexity... > > I said *explore* since as you all said, optimal highly depends on the > platform on which this will run, along with design criteria.OK. I'm frustrated. Why? Because I just gave you an automatic way to simplify it: separate the observable sub-system from the unobservable one. There are algorithms out there to do it, I learned about them when I was getting my Master's degree, and I've had absolutely no need for them in over 20 years of working on control systems in industry. So I'm not going to find the details for you. Scilab has a function call that does this: unobs. It gives you the number of unobservable states, and if you talk to it nicely it gives you a transformation matrix. If I understand the scanty help, that transformation matrix is what you need to go from the system you have to one that is nicely separated into observable and unobservable parts. A similar function exists for the controllable part, which you'll also need to use if you're handed a totally arbitrary system. So -- study up!!! I'm not sure what the use is, though. What are you proposing to _do_, that you're starting with ill-formed state-space descriptions? Wouldn't it be better to just not go there in the first place? -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
Reply by ●January 23, 20132013-01-23
On 1/23/13 11:39 AM, Tim Wescott wrote:> On Wed, 23 Jan 2013 09:26:05 -0600, gretzteam wrote: > >>> Your system has nine unobservable states. First delve into the control >>> systems literature to separate out the observable sub-system from the >>> unobservable one, then consider my suggestion about converting the >>> observable part to Jordanian form. >>> >>> -- >> >> >> Yes - hence why I was looking for an automatic way to simplify it. I >> gave this one as a *dumb* example since I happen to know the simplest >> implementation. >> >> Basically, I wonder if the problem of finding a transformation matrix T >> in order to *explore* the tradeoffs between the number of states, number >> of coefficients, coefficient complexity... >> >> I said *explore* since as you all said, optimal highly depends on the >> platform on which this will run, along with design criteria. > > OK. I'm frustrated. Why? Because I just gave you an automatic way to > simplify it: separate the observable sub-system from the unobservable > one. There are algorithms out there to do it, I learned about them when > I was getting my Master's degree, and I've had absolutely no need for > them in over 20 years of working on control systems in industry. So I'm > not going to find the details for you. > > Scilab has a function call that does this: unobs. It gives you the > number of unobservable states, and if you talk to it nicely it gives you > a transformation matrix. If I understand the scanty help, that > transformation matrix is what you need to go from the system you have to > one that is nicely separated into observable and unobservable parts. A > similar function exists for the controllable part, which you'll also need > to use if you're handed a totally arbitrary system. > > So -- study up!!! > > I'm not sure what the use is, though. What are you proposing to _do_, > that you're starting with ill-formed state-space descriptions? Wouldn't > it be better to just not go there in the first place? >Tim, i took one look at his/her 12-by-12 "A" matrix that was mostly zero, and right away i knew it was pretty much useless. gretzteam, you need to understand that people here are doing you a favor for no compensation or remuneration in return. don't crap on us for offering to do that. make the questions as concise and simplified as possible. at one time, i thought i understood a basis for a question regarding how one might start with an LTI system expressed in terms of unit delays (z^-1) and to transform it into a system expressed in terms of "diff" units, which i presume are (1 - z^-1). that's a question with meaning and specificity and can be answered. but now it appears that it isn't the question you want answered. so i am hesitant to put in any more effort than typing this post regarding it. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●January 23, 20132013-01-23
On 22.01.2013 22:31, gretzteam wrote:> Hi, > Given a state-space description of a digital filter, is it possible to find > a transformation matrix T so that the resulting representation is not only > 'minimal' (number of states), but also using the simplest > structure/coefficients? > > There are various methods to convert a given state-space into a > minimal-state. However, there are a ton of possible representations of > 'minimal', and the difference in implementation might be huge. > > As an example, a simple series of differentiators would have coefficients > +1/-1, and nothing else - trivial to implement. Now if starting from > another state space description (most likely with more states), is there > an algorithm that would get me to the differentiators? I can go back to the > correct number of states, but never in the form of differentiators. > > Thanks >EXAMPLE Let's assume a system ODE of 6th degree 1 y ' ' ' ' ' ' + 6 y ' ' ' ' ' + 15 y ' ' ' ' + 20 y ' ' ' + 15 y ' ' + 6 y ' + 1 y = 1 and then find an equivalent of a3 y ' ' ' + a2 y ' ' + a1 y ' + a0 y = 1 a1 = ? a2 = ? a3 = ? Solution 8,829499 y ' ' ' + 9,323845 y ' ' + 5,090062 y ' + 0,995073 y = 1 Start Value(s): x = 0 y (0) = -0,002559313 y ' (0) = 0,04918871 y ' ' (0) = -0,1581114 First you find a solution of ODE 6th degree and then use it to approximate to 3rd degree. JCH
