Subject: Table length reduction

From: "D. C. Sessions" <[email-masked]>
Date: Mon, 08 May 2000 10:29:44 -0700

OK, I said I'd have a go at a program to intelligently
reduce the size of IBIS tables so that we can have high
resolution where needed and still keep below the 100-point
limit.  Here is is, attached.  The language will look
very, very strange to most of you; it's Icon, an academic
language that's sort of a cross between C and Prolog.
You can get documentation and a copy for most any platform at
http://www.cs.arizona.edu/icon/

The program as written is pretty crude.  It takes JUST the
table data and thins it out using a cubic interpolation.
Command-line syntax is

decimate <pts> <file>

Where <pts> is the maximum number of points in the output,
and <file> is the source.  Output is to standard output, and
if no input file is specified it defaults to standard input.
It expects each line to have the same number of fields (and
will barf if they don't match).  For unjustifiable reasons it
does NOT accept scientific notation in; it does accept 'munp'
suffixes.  The output is scientific.  If I'd been more awake
I'd have done both in scientific and left formatting up to a
perl or awk script.

That said, I've experimented it several data sets and it seems
to produce reasonable results.  Feedback, improvements, or a
complete rewrite to C welcome.

-- 
D. C. Sessions
[email-masked]

# Data row: an independent variable and a set of dependent variables
record t_row( x, yvals )

# Get a sequence of words from a line of text,
# where the cset 'delim' separates words
procedure get_word( delim, line )
  local left, right, word
  left := right := 1
  while right <= *line do {
    left := many( delim, line, right ) | right
    right := many( &ascii -- delim, line, left ) | left
    suspend word := line[ left:right ]
    }
  end

# Convert a word to a numerical value.
# The numerical portion consists of the usual
# numerical prefix optionally followed by scale
# of the munp type.  Maybe if I get ambitious I'll
# add a scientific notation option.
procedure get_numeric( word )
  local base
  base := get_word( ~( &digits ++ '.-' ), word )
  return case word[ *base+1 ] of {
    "m"		: base / 1E3
    "u"		: base / 1E6
    "n"		: base / 1E9
    "p"		: base / 1E12
    default	: base
    } | base
  end

# Translate a table into a list of structures
procedure get_fn_set( source )
  local line, lineval, fn
  fn := []
  while line := read( source ) do {
    lineval := []
    every put( lineval, get_numeric( get_word( ' \t', line ) ) )
    put( fn, t_row( lineval[ 1 ], copy( lineval[ 2 : *lineval+1 ] ) ) )
    }
  return fn
  end

# Extract a single function from a list of structures
# In other words, select a single column from the dependent
# variable collection.
procedure get_single_fn( fn_set, column )
  local row, result
  result := []
  every row := !fn_set do
    put( result, t_row( row.x, row.yvals[ column ] ) )
  return result
  end

# Interpolate a value from at 'new_x' based on
# the values of the list of rows 'neighbors'
procedure interpolate( new_x, neighbors )
  local pick, flick, product, result
  result := 0
  every pick := !neighbors do {
    product := pick.yvals
    every ( flick := !neighbors ) ~=== pick do
      product *:= ( new_x - flick.x )/( pick.x - flick.x )
    result +:= product
    }
  return result
  end

# Get an interval of 2n+1 centered at 'ctr' if
# possible but bounded by 1 and 'mx'
procedure left_bound( ctr, n, mx )
  return if ctr < n + 1
    then 1
    else if ctr > mx - n
      then mx - ( n + n )
      else ctr - n
  end

# Select a list of 2* 'n' neighbors for 'row' from list 'fn'
# and return the selected list
procedure pick_window( row, n, fn )
  local lend, rend
  lend := left_bound( row, n, *fn )
  rend := lend + n + n
  return fn[ lend:row ] ||| fn[ row+1:rend+1 ]
  end

# Compare the interpolated value at a row to
# the actual value.  Return the relative error
procedure epsilon( row, n, fn, scale )
  local ival
  ival := interpolate( fn[ row ].x, pick_window( row, n, fn ) )
  return abs( ( ival - fn[ row ].yvals )/scale )
  end

# Build a table of error terms from a set of functions
# using an interpolation of order ( 2n-1 )
procedure err_tab( n, fn_set )
  local	cn, j, row, result, scale, column
  result := table( 0 )
  every insert( result, !fn_set, 0 )
  every cn := 1 to *(fn_set[1].yvals) do {
    column := get_single_fn( fn_set, cn )
    scale := 0
    every row := !column do scale := scale < abs( row.yvals )
    every j := 1 to *column do
      result[ fn_set[ j ] ] := result[ fn_set[ j ] ] < epsilon( j, 2, column, scale )
    }
  return result
  end

# Decide which table elements to keep and which to cull
# Start by culling the elements which have the least
# error values, but keep their neighbors for this pass
# Return an edited function list
procedure cull( n, fn_set )
  local pick, j, l, r, etab, index_tab, cull_list, cull_tab, fn_size
  fn_size := *fn_set
  etab := err_tab( n, fn_set )
  index_tab := table( 1 )
  cull_tab := []
  every j := 1 to fn_size do {
    insert( index_tab, fn_set[ j ], j )
    put( cull_tab, 0 )		# Start with the decision unknown
    }
  cull_tab[ 1 ] := 1		# keep the first and last elements
  cull_tab[ fn_size ] := 1
				# sort to a record list by values
  cull_list := sort( etab, 2 )[1:(fn_size/(n+n+1))]	# Limit the number of culls
  every pick := index_tab[ (!cull_list)[1] ] do
    if 1 > cull_tab[ pick ] then {
      cull_tab[ pick ] := -1	# Ditch it
      l := left_bound( pick, n, *fn_set )
      r := l + n + n
      every cull_tab[ pick ~= ( l to r ) ] := 1		# Keep the neighbors
      }
  result := []
  every pick := 1 to *fn_set do
    if cull_tab[ pick ] >= 0
      then put( result, fn_set[ pick ] )
#      else {
#        writes( "Culled " )
#	write_fn_line( fn_set[ pick ] )
#	}
  return result
  end

# Round off a number 'x' to 'n' digits precision
procedure roundoff( n, x )
  base := log( 10 )
  if x = 0
    then return 0
    else {
      scale := integer( log( abs( x ), 10 ) )
      fudge := integer( exp( ( n - scale )*base ) )
#      writes( "(" || n - scale || " " || fudge || ")" )
      return integer( x * fudge ) / real( fudge )
      }
  end

# Write out a line of a function
procedure write_fn_line( fn_line )
  local cwidth
  cwidth := 12
  writes( right( roundoff( 3, fn_line.x ), cwidth, " " ) )
  every writes( right( roundoff( 3, !fn_line.yvals ), cwidth, " " ) )
  write( )
  end

procedure main( argv )
  limit := pop( argv )
  source := open( pop( argv, src ) ) | &input
   fn_set := get_fn_set( source )
   foo := fn_set
   while *foo > limit do foo := cull( 2, foo )
   every bar := !foo do write_fn_line( bar )
  end

---

From: "Chris Rokusek" <[email-masked]>
Date: Mon, 8 May 2000 12:05:31 -0700

D.C.,

A Natural cubic spline will often introduce non-monotonicity resulting in
simulation instability or inaccuracies especially on diode curves.  You will
need to use a different spline.

Don't believe me?  Try

	http://www.glue.umd.edu/~tvp/interp.html

and draw a monotonic diode curve.

Chris Rokusek
Innoveda

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On Behalf Of
> D. C. Sessions
> Sent: Monday, May 08, 2000 10:30 AM
> To: IBIS Mailing list
> Subject: Table length reduction
>
>

---

From: "D. C. Sessions" <[email-masked]>
Date: Mon, 08 May 2000 12:47:43 -0700

> and draw a monotonic diode curve.

Chris, I'm not doing interpolation.  I'm using interpolation to cull
redundant points.  The algorithm works by calculating a spline from
the four points adjacent to a subject point and interpolating to
that point.  Those points with minimal discrepancy from the interpolation
are candidates for removal and their immediate neighbors are kept until
the next pass.

Then again, one of the things I love about Icon is that prototyping
is awesomely fast.  By all means try a different algorithm...

-- 
D. C. Sessions
[email-masked]

---

From: "Weston Beal" <[email-masked]>
Date: Mon, 8 May 2000 14:02:27 -0700

D.C.,

I think I understand what you're doing, but wouldn't it be easier and maybe
more applicable to do linear interpolation?  If the program (simulator or
translator) that reads the resulting IBIS file does cubic spline then you
are correct in doing the same in your filter.  If the IBIS file is going
into a program that does piece-wise linear interpolation then the filter
should do the same, I think.

On a related subject, what do ya'll think about a smoothing filter (least
square?) to reduce measurement noise in IBIS tables?  Is it useful or
dangerous?

Regards,
Weston

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]On Behalf Of
D. C. Sessions
Sent: Monday, May 08, 2000 12:48 PM
To: IBIS Mailing list
Cc: Chris Rokusek
Subject: Re: Table length reduction

--
D. C. Sessions
[email-masked]

---

From: "D. C. Sessions" <[email-masked]>
Date: Mon, 08 May 2000 14:24:42 -0700

> should do the same, I think.

Actually, the program is general.  You could set n=1 in the top-level
procedure instead of 2 and it would be linear instead of cubic.  On the
other hand, cubic is MUCH nicer from a harmonic-minimization standpoint
and in principle lets the software use fewer piecewise segments, thus
speeding up simulation.  If you hold the number of points constant, the
linear method will concentrate them at high-curvature regions (e.g., at
the beginning and end of a rise) and the cubic will concentrate them
before the rise, just after the beginning, before the end, and just after
the end.  Sort of.

You have source code -- play with it and see what it does. 

> square?) to reduce measurement noise in IBIS tables?  Is it useful or

I wouldn't use least-squares.  At model generation time I'd burn the
cycles to do a Fourier transform and filter the stuff beyond the range
of validity.

-- 
D. C. Sessions
[email-masked]

---

From: "Chris Rokusek" <[email-masked]>
Date: Mon, 8 May 2000 14:31:58 -0700

D.C.,

Understood.  I see that what you're doing seems to be fairly independent of
the choice of spline.  Although the choice of spline would definately change
the answer it seems that since you're not introducing any new points it does
not introduce an error (just perhaps removes different points).

Could you describe the error function in more depth (I don't trust my
Icon-ese)?  Does it work well for small values near 0.0?

Chris Rokusek
Innoveda

> > > From: [email-masked]
> [mailto:[email-masked]]On Behalf Of
> > > D. C. Sessions

---

From: "D. C. Sessions" <[email-masked]>
Date: Mon, 08 May 2000 14:45:20 -0700

> Icon-ese)?  Does it work well for small values near 0.0?

The first time through I used relative error, but on reflection (!) I
decided that people weren't using IBIS for noise analysis in the time
before a transition.  So instead, I just took the absolute difference
between the input point and the interpolated value and called it good.

In order to compare typ/min/max on more or less equal footing, the
errors for each are normalized to the largest absolute value in each
column.  The largest error term for each row is used to sort the
rows, and the (table length)/(2n+1) smallest error rows are
candidates for culling.  For a cubic, this means that 20% of the
table could be culled in each pass.

To answer the direct question, near zero isn't special.

-- 
D. C. Sessions
[email-masked]

---

From: "Chris Rokusek" <[email-masked]>
Date: Mon, 8 May 2000 15:32:48 -0700

D.C.,

The more I think about this, the more I believe an even better solution is
that the error function be computed for BOTH a linear and cubic spline and
then a given point can only be removed if it simultaneously below a limit
(or within a percentile) for both.  This would prevent the cubic spline from
removing elbows and keep linear from removing points in the curve "where
there is about to be a change."

Even with this contraint, it seems like there still be a lot of truly
worthless points removed which is the whole point of the excersise.  What do
you think?

Another observation:  Since the algorithm computes all the error values as a
first pass and then begins culling starting with the lowest error first, it
seems as though the error values near (2 neighbors) the first removed point
are now invalid (cause they depended on the removed point) and this should
be taken into consideration somehow (either by not allowing the neighbors to
be culled or recomputing the error for the neighbors).

Is it getting hairy enough yet?

Chris Rokusek
Innoveda

> From: Weston Beal [mailto:[email-masked]]
> Sent: Monday, May 08, 2000 2:02 PM
> To: 'IBIS Mailing list'
> Subject: RE: Table length reduction
>
>
> D.C.,
>

---

From: "D. C. Sessions" <[email-masked]>
Date: Mon, 08 May 2000 17:17:18 -0700

> there is about to be a change."

Sounds good, but since this is done on a sort basis there needs to be
a scalar metric for prioritizing culls.  Looks like you may have to
learn Icon yet, Chris!

> worthless points removed which is the whole point of the excersise.  What do

Don't see why not.  In general, though, a linear interpolation is just
a very special case of cubic.  Maybe the linear will accomplish what
you want.

> be culled or recomputing the error for the neighbors).

Already done.  The algorithm culls the least-error point, then marks its four
neighbors as keepers until the next pass, when the errors are all recalculated.

> Is it getting hairy enough yet?

I'm just rusty enough on the math that I don't know if there's a real chance
of later cullings increasing the error for points culled earlier to unacceptable
degree.  That's one of the reasons I put this thing out -- to have people push
real datasets through it to see if the results are OK.

-- 
D. C. Sessions
[email-masked]

---

From: raghu <[email-masked]>
Date: Wed, 10 May 2000 15:43:55 -0700

D.C.,

The table length reduction scheme looks very attractive. One could start with much more than 100 points and reduce them
to 100 "good" points. If you are talking about v-t curves, for example, how do you ensure that the same time points are
good for typ, min, or max. The table, I think, can have only 100 time points and they have to be the same for typ, min,
or max. Or is it your experience that this is not such a big constraint?

Best regards,

-- 

************************************************************************
Raj Raghuram                       
Applied Simulation Technology                 
1641 N. First Street, Suite 170                       
San Jose, CA-95112.                      
Tel: (408) 436-9070 ext.101
Fax: (408) 436-9078
e-mail: [email-masked]
************************************************************************

---

From: "D. C. Sessions" <[email-masked]>
Date: Wed, 10 May 2000 15:51:12 -0700

> or max. Or is it your experience that this is not such a big constraint?

The published software takes the greatest error of the for typ, min, and max.
That way, if deleting a line would mess up any of the three it gets kept.

-- 
D. C. Sessions
[email-masked]