Pulse domain linear programming circuit

A system for making a pulse domain linear programming circuit. The inputs and the outputs to the pulse domain linear programming circuit are time encoded pulse signals. The circuit includes arrays of two types of cross-coupled time encoding elements. The first type of elements includes two integrators, adders, a hysteresis quantizer, and a 1-bit self-feedback DAC. The second type of elements includes a bias element, a leaky integrator, adders, a fixed memory-less non-linearity, a regular integrator, a hysteresis quantizer and a 1-bit self-feedback DAC. The cross-coupling signals between the two types of elements are pulse time-encoded signals. All of the cross-coupling weights are set via 1-bit DACs having variable gains. The cross-coupling weights are used to set a constraint equation of a pulse domain linear programming problem. Methods to make the foregoing circuit are also described.

INCORPORATION BY REFERENCE

are each hereby incorporated by reference in their entirety along with the Provisional Application identified above.

BACKGROUND

1. Technical Field

This disclosure is generally related to circuits for linear programming and in particular to pulse domain linear programming circuits.

2. Description of Related Art

Typically, a circuit performing time encoding does not process or solve a linear programming problem. Linear programming is a well known mathematical technique for finding an optimized answer to many practical problems in operations research and in many technological arts as well, such as recovery of signals captured by compressed sensing.

Prior art circuits solve linear programming problems using conventional analog signals. Consequently, such prior art circuit utilize analog amplifiers. The accuracy of such prior art circuits is limited by the linearity of the analog amplifier, commonly used in an internal input.

FIG. 1shows a prior art analog-input time encoder. See also reference 1 identified above. This circuit has a single analog input u(t) and a single pulse output z(t). This circuit encodes analog input signals u(t) into pulse signals z(t). If the analog signal is bandlimited, the encoding can be practically without loss of information. That is, the input u(t) can be recovered from the timing of the output signal z(t). A time decoding machine can be used to recover the analog input u(t) from the asynchronous pulse output z(t). Assuming ideal elements, practically no quantization error is introduced by this encoder. The circuit ofFIG. 1has an input analog linear amplifier (g1), an integrator, a hysteresis quantizer, a feedback element (g3), and an adder (+). This circuit is not used for linear programming or other optimization problems.

FIG. 2shows a prior art circuit to solve a linear programming problem in an analog domain. See prior art reference 2 identified above. This circuit has n analog inputs and N analog outputs. The circuit ofFIG. 2can solve problems of the type

where A is a constraint matrix with n rows and N columns, Y is an input column vector of n analog numbers, Z is an output column vector of N analog numbers, and f is a linear function of the output vector. All of the signals in the circuit ofFIG. 2are conventional analog signals. The circuit ofFIG. 2is shown in a vector symbolic form. The matrix multiplication symbols represent arrays of variable-gain analog amplifiers, such as analog multipliers, and adders. The accuracy of this circuit is limited by the linearity of these variable-gain analog amplifiers.

BRIEF DESCRIPTION OF THE INVENTION

Embodiments of the present disclosure provide a system and method for making a pulse domain linear programming circuit. The inputs and the outputs to the pulse domain linear programming circuit are time encoded pulse signals.

The circuit includes arrays of two types of cross-coupled time encoding elements. The first type of elements includes two integrators, adders, a hysteresis quantizer, and a 1-bit self-feedback DAC.

The second type of elements includes a bias element, a leaky integrator, adders, a fixed memory-less non-linearity, a regular integrator, a hysteresis quantizer and a 1-bit self-feedback DAC. The cross-coupling signals between the two types of elements are pulse time-encoded signals. All of the cross-coupling weights are set via 1-bit DACs having variable gains. The cross-coupling weights are used to set a constraint equation of a pulse domain linear programming problem.

The present disclosure also includes a method of making a circuit for linear programming in the pulse domain. The method includes providing a linear time encoder having an input, the input including a first adder, and an output, providing at least a first cross-connection element and a second cross-connection element, each having an input and an output, and connecting the output of the linear time encoder to the input of the first cross-connection element. The method may further include providing a non-linear time encoder having an input, the input including a first adder, and an output, connecting the output of the first cross-connection element to a first input of the first adder of the non-linear time encoder, connecting the output of the non-linear time encoder to the input of the second cross-connection element, and connecting the output of the second cross-connection element to an input of the first adder of the linear time encoder.

Other systems, methods, features, and advantages of the present disclosure will be, or will become apparent, to a person having ordinary skill in the art upon examination of the following drawings and detailed description. It is intended that all such additional systems, methods, features, and advantages included within this description, be within the scope of the present disclosure, and be protected by the accompanying claims.

DETAILED DESCRIPTION

The present disclosure relates a system and method for making a pulse domain linear programming circuit. Specifically, the pulse domain linear programming circuit can be used for a real-time recovery of signals captured via compressed sensing, in which a linear programming optimization problem is solved in a pulse domain.

FIG. 3shows a block diagram of a pulse domain linear programming circuit300of the present disclosure, suitable for solving the linear programming problem of Equation 1 in the pulse domain. The pulse domain linear programming circuit300does not need analog variable-gain amplifiers used in the prior art (FIG. 2). The pulse domain linear programming circuit300, for example, solves in the pulse domain the following linear programming problem:
Min|Z|1subject toA*Z=Y,Z0.

That is, minimize |Z|1subject to the above constraint. |Z|1is the norm-1 of the vector Z. |Z|1is defined as:
|Z|1=Zi,the summation range beingi=1 toN.

As a person having an ordinary skill in the art will appreciate, an arrow entering a block or a symbol indicates an input and an arrow leaving a block or a symbol indicates an output. Similarly, connections described below may be of any electromagnetic type, such as electrical, optical, radio-frequency, and magnetic.

The circuit ofFIG. 3is shown in vector form. The input for the circuit300is a vector of signal of size n. The output is a vector of signals of size N. The number of outputs, N, is larger than the number of inputs, n. Each signal line or arrow represents a signal bus. Each bus has size n or N as shown inFIG. 3. Each bus is implemented by a group of n or N wires. Each block symbol, such as integrators, quantizers, 1-bit DACs, shown inFIG. 3represents a parallel array of actual circuit elements, such as array of integrators, array of quantizers, array of 1-bit DACs, and so on. The pulse domain linear programming circuit300includes n number of the linear time encoders, n×N number of the first cross-connection elements306, N×n number of the second cross-connection elements310, and N number of the non-linear time encoders308.

The first component of circuit ofFIG. 3is a time encoder block348. This block348is also labeled as TE1and is located at the left side ofFIG. 3. This block348is an array of n individual time encoders. Block348is optional and therefore does not need to be a part of the pulse domain programming circuit300. This block348is used, if needed, to convert analog input data Y into the time encoded pulse domain Yp. This block348is not required in those applications in which the input data is already in the time encoded pulse domain. If the input data356is in the analog domain then each of the n individual time encoders348of the array of time encoders may be implemented by a prior art time encoder such as the prior art time encoder depicted byFIG. 1. This array of time encoders348converts the analog input vector, Y, into a pulse time encoded vector, Yp. Both Y and Ypare vectors of size n.

The vector Ypis fed into the input bus, of size n, of the pulse domain programming circuit300. This bus is connected into an first adder312of a linear time encoder304. The adder312is actually composed of an array of n individual adders. Each individual adder312of the array of adders in an array, of size n, of linear time encoders304combines one individual element of Ypwith one individual feedback signal.

Each linear time encoder304of the array of linear time encoders preferably includes a first integrator314, a second adder316, a second integrator318, a hysteresis quantizer320and a 1-bit DAC (g3)322. Each of these elements are preferably implemented as an array of elements of size n in order to form the array of linear time encoders304.

Considering an individual instance of a linear time encoder304, an output of the first adder312is connected to an input of the first integrator314, an output of the first integrator314is connected to a first input316A of the second adder316. An output of the second adder316is connected to an input of the second integrator318, an output of the second integrator318is connected to an input of the hysteresis quantizer320, and an output of the hysteresis quantizer320is provides the output of the linear time encoder304. It should be noted that the hysteresis quantizer320is merely an exemplary quantizer and other types of quantizers may also be utilized.

Considering the linear time encoder304as an array of size n, the outputs of the array of adders312are each connected to an integrator314in an array of n individual integrators314. The outputs of the array of integrators314are each connected to a second adder316in an array of n individual adders316. Other blocks at the top half ofFIG. 3are the second integrator318(implemented as array of n individual integrators318), a hysteresis quantizer320(formed by array of n individual hysteresis quantizers320) and a self-feedback elements g3(preferably consisting of an array of n 1-bit DACs322).

The pulse domain linear programming circuit300includes an array of size n of linear time encoders304having an input and an output. A array of first cross-connection elements306and an array of second cross-connection elements310, each having inputs and outputs, couple the array of size n of linear time encoders304to an array of size N of the of non-linear time encoders308shown in the lower portion ofFIG. 3and also shown byFIG. 3a.

Considering an individual instance of the non-linear time encoder308, it has an input coupled to a first adder326and an output, the output of an instance of the first cross-connection element306being connected to a first input326A of the first adder326of the non-linear time encoder308and the output of the non-linear time encoder308being connected to the input of the second cross-connection element310. The output of an instance the second cross-connection element310is connected to a second input312B of the first adder312of the linear time encoder304. Each instance of non-linear time encoder308includes the first adder326having a second input326B and an output, a second adder328having a first input328A, a second input328B, a third input328C, and an output, a first integrator332having an input and an output, a non-linear element336having an input and an output, a third adder338having a first input338A, a second input338B, and an output, a second integrator340having an input and an output, a hysteresis quantizer342having an input and an output, a first self-feedback element334having an input and an output, a second self-feedback element346having an input and an output, a third self-feedback element344having an input and an output, and a bias element330having an output. The output of the first adder326is connected to a first input328A of the second adder328, the output of the second adder328is connected to the input of the first integrator332, the output of the first integrator332is connected to the input of the non-linear element336, the output of the non-linear element336is connected to the first input338A of the third adder338, the output of the third adder338is connected to the input of the second integrator340, the output of the second integrator340is connected to the input of one of the hysteresis quantizer342, the output of hysteresis quantizer342is connected to the output of the non-linear time encoder308giving waveform352as Zpor360, the output of the bias element330is connected to the second input of328B the second adder328, the output of the first integrator332is connected to the input of the first self-feedback element334, the output of the first self-feedback element334is connected to the third input328C of the second adder328, the output of the hysteresis quantizer342is connected to the inputs of the second and third self-feedback elements346and344, the output of the second self-feedback element346is connected to the second input326B of the first adder326and the output of the third self-feedback element344is connected to the second input338B of the third adder338. Self-feedback elements334,344and346are each preferably implemented by 1-bit DACs. The transfer function of non-linear element336is shown inFIG. 3. Regarding the transfer function of non-linear element336, when its input is less or equal to zero the nonlinear circuit336should provide an output equal to zero. For inputs larger than zero the output should increase (but not necessarily linearly) as the input is increased. The transfer function shown inFIG. 3for non-linear element336has both a break point and a slope. To get a proper solution of the equations, the breakpoint should be set to 0 and the slope to a positive value. A typical value of the slope is 1.

InFIG. 3each triangular drawing with a label g3represents an array of 1-bit DAC's, with each individual DAC having gain equal to g3, while each triangular drawing with a label I (Identity) represents an array of 1-bit DAC's, with each individual DAC having gain equal to one.

Considering the non-linear time encoder308as an array of size N, the outputs of the array of adders326are each connected an input328A in an array of adders328whose outputs are connected to to an integrator314in an array of N individual integrators314. The non-linear time encoder308has several adders blocks326,328,338(each one is an array of N individual adders), two integrators332and340(each formed by an array of N integrators), a nonlinear element336(formed by an array of N nonlinear elements) a hysteresis quantizer342(formed by an array of N individual hysteresis quantizers) and three self-feedback elements334,344and346(each one consisting of an array of N 1-bit DACs.) The first integrator332and the self-feedback element334from its output to its input, is equivalent to just one leaky integrator block333(formed by an array of N individual leaky integrators), which can be directly and efficiently implemented in VLSI. The bias element330is used to provide a set of N constant values that determine the function f to be minimized. The circuit ofFIG. 3can accept values from the bias block either in analog format or in pulse time encoded format.

The function f is a linear function as shown below

where the bicoefficients are the N outputs of the bias element330.

The N non-linear time encoders308implement, in the pulse domain, the dynamics of N coupled non-linear first order differential equations. The n linear time encoders304implement, in the pulse domain, the dynamics of n coupled linear first order differential equations.

InFIGS. 3 and 3a, the output Zp360of the pulse domain linear programming circuit300is optionally connected to an input of an array of lowpass filters354, with the array of the lowpass filters354outputting an analog output362.

Circuit300includes an array of size n of linear time encoders304, an array of first cross-connection elements306, an array of second cross-connection elements310, an array of size N of non-linear time encoders308, and optionally an array of size n of time encoders348, and an array of lowpass filter354having an input of size n.

It should be noted here that the waveforms324,350, and352represent time encoded pulses at respective locations depicted inFIG. 3.

The pulse domain linear programming circuit300contains first and second cross-connection elements306and310, labeled A and AT(transpose of matrix A). The first and second cross-connection elements306and310contain an array of N×n individual 1-bit DACs. Each 1-bit DAC may be very compact, including. for example, a simple switch that can be implemented with as few as two transistors in VLSI and can operate at high speed, and is intrinsically linear due to a two-state operation. The gains of the N×n individual 1-bit DACs310-11through310-nN (seeFIG. 3b) are the values of the N×n entries of the matrix A of Equation 1. As such, A is shown as in input to pulse domain linear programming circuit300at the bottom ofFIG. 3.

InFIG. 3each triangular symbol with label A or ATrepresents a two dimensional array of 1-bit DACs. The array contains n×N individual DACs. Each individual 1-bit DAC of each array has a single voltage input and a single current output. The inputs, outputs, and the internal structure of the complete arrays (seeFIG. 3b) are as follows:

(a) For the case of the triangular symbol310with label A there are N inputs and n outputs. The array of individual 1-bit DACs are typically arranged as a two dimensional structure with N rows and n columns, with one individual one-bit DAC310-11-310-nN in each location. Each one of the N input wires (encoding N voltage signals) in1-inNfed the inputs of all the individual DACs located in each one of the N rows of the two dimensional array. Each one of the n output wires (encoding n current signals) out1-outnis connected to the outputs of all the individual DACs located in each one of the n columns of the two dimensional array. Note that the currents of all individual DACs in each column are summed together by just connecting their outputs together. Each individual one-bit DAC has a gain identified by the letters g11-gnN. Those gains are set according to the values of matrix A of Equation 1 as explained above.

(b) For the case of the triangular symbol306with label ATthere are n inputs and N outputs. The array of individual 1-bit DACs are typically arranged as a two dimensional structure with n rows and N columns, with one individual DAC in each location. Each one of the n input wires (encoding n voltage signals) fed the inputs of all the individual DACs located in each one of the n rows of the two dimensional array. Each one of the N output wires (encoding N current signals) is connected to the outputs of all the individual DACs located in each one of the N columns of the two dimensional array. Note that the currents of all individual DACs in each column are summed together by just connecting their outputs together. By interchanging the capital N's and the lowercase n's and the number306for the number310inFIG. 3b, the circuitry for the array AT306will be apparent.

FIG. 4illustrates an input-output characteristic of an exemplary hysteresis quantizer320,342. There are two possible output levels, −1 and +1, defined by arrows having reference numerals474,476,478, and480. The vertical axis470, indicating Vp[V], and horizontal axis472, indicating Vy[V], make the graph. The transition between the two output levels occurs at two different input trigger voltage levels. In an example described below, these trigger voltage levels are normalized to −1V and +1V. They are shown in the horizontal axis472of the graph. These values can be scaled, as suited for a particular VLSI implementation, without changing the basic operation of the circuit.

The pulse domain linear programming circuit300output is represented by the vector Zp360. This vector360is of size N. The size of the vector360is larger than that of the input vector Yp358. The output depends on the input data, the weights of the 1-bit DACs (of the first and second cross connect elements306and310) being the entries of the matrix A of Equation 1, and the data of bias element330defining the function f of Equation 1.

The vector Zp360contains the time encoded data. The output becomes valid after the pulse domain linear programming circuit300has settled to a steady state. The output360can be optionally converted to analog data Z362for evaluation. The conversion to analog data362can be done by using a low pass filter354, also labeled “LP,” which may be formed by an array of N individual low pass filters354. The analog output362is the vector Z, of size N.

In an illustrative simulation, operation of the pulse domain linear programming circuit300having random inputs and random constraints (entries of matrix A) has been simulated. The pulse domain linear programming circuit300converges to a solution expected from traditional algorithms. Below is shown an exemplary operation of the pulse domain linear programming circuit300for this simulation and a summary of the parameters and data used:

The size of the input vector was n=4

The size of the output vector was N=6. Thus the matrix A was of size n×N=4×6=24 elements.

The input vector for this simulation was:

The matrix A was:

The bias coefficients were set to 1. This sets the linear function to be minimized as the addition of all of the six entries of the output vector, as indicated below:

FIG. 5shows outputs of the pulse domain linear programming circuit300during a transient of this illustrative simulation, featuring a plot with the six outputs (Z1, Z2, . . . , Z6) settling over time. It can be observed that the outputs reach a steady constant state. The steady final values correspond to a solution of the linear programming problem of this illustrative simulation.

FIGS. 6(a) and6(b) illustrate a comparison of outputs of the linear programming circuit of the present disclosure (seeFIG. 6(a)) to ideal outputs (seeFIG. 6(b)). The six outputs of the pulse domain linear programming circuit300(steady values fromFIG. 5)with desired ideal values calculated by solving the linear programming problem of the example by a standard, non real-time, digital algorithm, in a MATLAB® simulation. InFIG. 6(a), Zirepresent the output values produced by the pulse domain linear programming circuit300, while inFIG. 6(b) Xirepresent desired ideal values. It can be observed the pulse domain linear programming circuit300solution is correct for all six values.

An advantage of the pulse domain linear programming circuit300is an ability to solve the linear programming problem by a circuit that operates in parallel and can provide the solution in real time as digital algorithms typically cannot operate in real time. The pulse domain linear programming circuit300does not require linearity-limiting feedback analog amplifiers whereas standard analog circuits require such amplifiers.

The pulse domain linear programming circuit300can be efficiently implemented in VLSI technology. The pulse domain linear programming circuit300can be compact with only three transistors required for each individual 1-bit DAC using DAC designs known in the prior art. In a state-of-the-art InP technology, the pulse domain linear programming circuit300can operate with a pulse rate of approximately 23 GHz, and can solve a typical linear programming problem in less than 10 ns. The gains g3of one bit DACs322and344are typically the same value and are adjusted as needed to set the pulse rate of the circuit300. For a pulse rate of 23 GHz, the gain g3should be about 4.6 mA/volt assuming a typical integrator (for integrators318and340) implemented with a capacitor of 100 fF and using InP technology for the devices. In such an embodiment, integrators314and332can be implemented using capacitors having a values of equal to two to three orders of magnitude greater than than of capacitors318or340so that the time constant of the circuit is typically to two and three orders of magnitude longer than the pulse time period.

The pulse domain linear programming circuit300can solve linear programming substantially in real time because: it operates in parallel, the internal components arc compact (allows large amount of parallelization), and the internal components can operate at high speed. The pulse domain linear programming circuit300has a parallel architecture. Two asynchronous 1-bit DACs are required in cross connection elements306and310for each element of the matrix A. Each 1-bit DAC is a very compact circuit that requires only three transistors. This allows the implementation of large circuit arrays in a single integrated circuit chip.

Each asynchronous 1-bit DAC can operate at very high speed (˜10 GHz range in a standard 90 nm CMOS technology and ˜60 GHz in an InP HBT technology). The other components of the architecture (hysteresis quantizers and analog integrators) can also operate at similar speeds.

FIG. 7is a flowchart of a method700of making the pulse domain linear programming circuit300. The method700includes providing a linear time encoder having an input, the input including a first adder, and an output (block702), providing at least a first cross-connection element and a second cross-connection element, each having an input and an output (block704), connecting the output of the linear time encoder to the input of the first cross-connection element (block706), providing a non-linear time encoder having an input, the input including a first adder, and an output (block708).

The method700may further include connecting the output of the first cross-connection element to a first input of the first adder of the non-linear time encoder (block710), connecting the output of the non-linear time encoder to the input of the second cross-connection element (block712), connecting the output of the second cross-connection element to an input of the first adder of the linear time encoder (block714).

In the method700, the providing the linear time encoder may further include:

providing a first integrator, providing a second adder, providing a second integrator, providing one of a quantizer having an output and a hysteresis quantizer having an output, connecting an output of the first adder to an input of the first integrator, an output of the first integrator to a first input of the second adder, connecting an output of the second adder is connected to an input of the second integrator, connecting an output of the second integrator to an input of one of the quantizer and the hysteresis quantizer, and connecting an output of one of the quantizer and the hysteresis quantizer to the output of the linear time encoder.

Still further, in the method700, the connecting the output of the hysteresis quantizer further includes connecting an amplifier between one of an output of the quantizer and an output of the hysteresis quantizer and a second input of the second adder. It may be emphasized here that connecting the hysteresis quantizer is just an illustrative option since the method may also include connecting another type of quantizer.

In order to make an array including various elements described above, the method700may further include providing a plurality of the linear time encoders, providing a plurality of the first cross-connection elements, providing a plurality of the second cross-connection elements, and providing a plurality of the non-linear time encoders.

In the method700, the providing the linear time encoder further includes connecting the input of the linear time encoder to a pulse time encoded signal. The connecting the input of the linear time encoder further includes generating the pulse time encoded signal from an analog signal processed by a time encoder. The providing the non-linear time encoder further includes connecting the output of the non-linear time encoder to an input of a lowpass filter, an output of the lowpass filter outputting an analog output.

Regarding the providing the non-linear time encoder, the method700may include providing the first adder to have a second input and an output, providing a second adder to have a first input, a second input, a third input, and an output, providing a first integrator to have an input and an output, providing a non-linear element to have an input and an output, providing a third adder to have a first input, a second input, and an output, providing a second integrator to have an input and an output, providing one of a quantizer and a hysteresis quantizer, each to have an input and an output, providing a first self-feedback element to have an input and an output, providing a second self-feedback element to have an input and an output, and providing a bias element to have an output, and connecting the output of the first adder to a first input of the second adder, the output of the second adder being connected to the input of the first integrator, connecting the output of the first integrator to the input of the non-linear element, connecting the output of the non-linear element to the first input of the third adder, connecting the output of the third adder to the input of the second integrator, connecting the output of the second integrator to the input of one of the quantizer and the hysteresis quantizer, connecting the output of the one of the quantizer and the hysteresis quantizer to the output of the non-linear time encoder, connecting the output of the bias element to the second input of the second adder, connecting the output of the first integrator to the input of the first self-feedback element, connecting the output of the first self-feedback element to the third input of the second adder, connecting the output of the one of the quantizer and the hysteresis quantizer to the input of the second self-feedback element, and connecting the output of the second self-feedback element to the second input of the first adder.

In the method700, the connecting the output of the one of the quantizer and the hysteresis quantizer further includes providing an amplifier having an input and an output, connecting the input of the amplifier to the output of the one of the quantizer and the hysteresis quantizer and connecting the output of the amplifier to the second input of the third adder.

Still further, in the method700, the providing the first cross-connection element further includes providing a plurality of digital-to-analog converters having at least one bit. The providing the second cross-connection element further includes providing a plurality of digital-to-analog converters having at least one bit.

The foregoing method700or elements of the method700may also be stored on a computer-readable medium having computer-executable instructions to implement the method700or the elements of the method700.

As a person having ordinary skill in the art would appreciate, the elements or blocks of the methods described above could take place at the same time or in an order different from the described order.

It should be emphasized that the above-described embodiments are merely some possible examples of implementation, set forth for a clear understanding of the principles of the disclosure. Many variations and modifications may be made to the above-described embodiments of the invention without departing substantially from the principles of the invention. All such modifications and variations are intended to be included herein within the scope of this disclosure and the present invention and protected by the following claims.