White-noise analysis and related methods of nonlinear systems identification describe a physical system's response to its input in terms of "kernels" of progressively higher orders. A popular analytic scheme in the laboratory uses a class of pseudorandom binary sequences, m-sequences, as a test signal. The m-sequence method has several advantages for investigating linear and nonlinear systems: ease of implementation, rapid calculation of system kernels, and a solid theoretical framework. One difficulty with this method for nonlinear analysis comes from the algebraic structure of m-sequences: linear and nonlinear terms can be confounded, especially in the analysis of systems with many inputs.

We have developed a modification of the m-sequence method which allows control of these anomalies. This method is based on input signals consisting of a superposition of m-sequences whose lengths are relatively prime. The fast computational methods which facilitate kernel calculation for a single m-sequence input are readily extended to this new setting. We describe the theoretical foundation of this method and present an application to the study of ganglion cells of the macaque retina.
top nutshell diagram technotes background reading

We consider estimation of the first- and second-order kernels for a system with two inputs.

Inputs

Second-order self- and cross-kernels

To estimate the second-order kernels, cross-correlate the response R(t) against the product of the underlying m-sequences m_[1](t) and m_[1](t):

• Beginning at (t_[1],t_[2]) = (0,0), C^1,2(t_[1],t_[2]) contains an estimate h^{^1,2}_[1,1](t_[1],t_[2]) of the second-order self-kernel h_[1,1](t_[1],t_[2]) with respect to the first input.
• Beginning at (t_[1],t_[2]) = (T₁,T₂), C^1,2(t_[1],t_[2]) contains an estimate h^{^1,2}_[2,2](t_[1],t_[2]) of the second-order self-kernel h_[2,2](t_[1],t_[2]) with respect to the second input.
• Beginning at (t_[1],t_[2]) = (0,T₂), C^1,2(t_[1],t_[2]) contains an estimate h^{^1,2}_[1,2](t_[1],t_[2]) of the second-order cross-kernel h_[1,2](t_[1],t_[2]).
• Beginning at (t_[1],t_[2]) = (T₁,0), C^1,2(t_[1],t_[2]) contains an independent estimate h^{^1,2}_[2,1](t_[1],t_[2]) of the second-order cross-kernel h_[2,1](t_[1],t_[2]). Note that h_[2,1](t_[1],t_[2]) = h_[1,2](t_[2],t_[1]).

Diagrammatic view of the algorithm for second-order kernels

The key to the algorithm is that because the m-sequence lengths M₁ and M₂ are relatively prime, all pairs of values of t₁ and t₂ occur exactly once, as t ranges from 0 to M₁M₂ - 1. This allows encoding of a function of two times (i.e., the second order-kernels) within a function of one time (the cross-correlation). It also allows us to "factor" the calculation of the cross-correlation into two stages.
top nutshell diagram technotes background reading

Technical notes

• Variants of the inverse-repeat method should be used to help remove higher-order "contaminants" from the kernel estimates.
• This approach is not limited to only two inputs. Each input is provided with a signal s_[j](t), with distinct taps (e.g., spaced by T₁ and T₂) into each of the underlying m-sequences. The practical limit to the number of inputs is determined by the ratio of the shortest m-sequence length to the minimum tap separation (which is the anticipated timespan of the kernels).
• In principle, this approach is not limited to second-order kernels. For estimation of kth-order kernels, the analogous procedure relies on k m-sequences, each of relatively prime length. Each input is a sum of these k sequences, and has a repeat length equal to the product of the repeat lengths of the underlying m-sequences. For more than two inputs, additional taps in each sequence (beyond the two taps 0 and T_j for each sequence m_j) should be used.
• Other nearly shift-orthogonal sequences besides m-sequences can be used, to avoid restrictions due to the limited set of repeat periods (7, 15, 31, 63, etc.) provided by m-sequences. Such sequences can be constructed for any length of form p = 4n-1, from the sequences of quadratic residues (mod p). However, the fast m-transform cannot be used to calculate cross-correlations with respect to these sequences.

Background reading on m-sequences

The m-sequence method and the inverse-repeat idea

The fast m-transform