Douglas A Castro

Sônia M Gomes
email: soniag@ime.unicamp.branamaria

Anamaria Gomide

Andrielber S Oliveira

Jorge Stolfi
email: stolfi@ic.unicamp.br

Multiresolution analysis on multidimensional dyadic grids

We propose a modified adaptive multiresolution scheme for representing d-dimensional signals which is based on cell-average discretization in dyadic grids. A dyadic grid is an hierarchy of meshes where a cell at a certain level is partitioned into two equal children at the next refined level by hyperplanes perpendicular to one of the coordinate axes which varies cyclically from level to level. Adaptivity is obtained by interrupting the refinement at the locations where appropriate scale (wavelet) coefficients are sufficiently small. One important aspect of such multiresolution representation is that we can use a binary tree data structure in all dimensions, that helps to compress data while still being able to navigate through it. Dyadic grids provide a more gradual refinement as compared with traditional multiresolution analyses that use, for instance, different quad-trees or oct-trees in 2D or 3D multiresolution applications. The cells may have different scales in different directions, this property can be explored to improve data compression of signals having anisotropic aspects.

Introduction

In recent years, many multiscale techniques have been used to provide more efficient algorithms than those that use just one level of resolution. In such frameworks, the differences between the information at consecutive levels of refinement are computed, and only the significant coefficients are stored. These are the principles of wavelet compression which have being successfully applied in many different contexts [START_REF] Cohen | Wavelet Methods in Numerical Analysis[END_REF]. For example, multiresolution finite volume schemes of Müller [START_REF] Muller | Adaptive Multiscale Schemes for Conservation Laws[END_REF] and Domingues et al. [START_REF] Domingues | An adaptive multiresolution scheme with local time-stepping for evolutionary pdes[END_REF] use adaptive grids that are dynamically obtained by taking local regularity information indicated by wavelet coefficients in the context of multiresolution analysis for cell averages of signals. Such adaptive discretizations allow the efficient solution of problems with vastly different scales of detail in different parts of the domain. For computational efficiency, one important aspect of such multiresolution methods is the topology of the mesh and data structure used to represent it. Often quad-grids and oct-grids are used for 2D and 3D domains, respectively, represented by quad-tree and oct-tree data structures [START_REF] Bihari | Multiresolution schemes for the numerical solution of 2-d conservation laws[END_REF]. We describe here a type of mesh, the dyadic grid, that can be efficiently represented by a binary tree, in domains of arbitrary dimension. For illustration, we apply adaptive dyadic grids to multiresolution analysis, using cell averaging as the discretization method. The paper is organized as follows. In Section 2 we define dyadic grids and related concepts. In Section 3 we present a general overview of multiresolution analysis. Section 4 contains numerical results on sample problems to show the efficiency of the proposed scheme.

Dyadic grids

Let the coordinates of R d be indexed from 0 to d -1. An infinite dyadic grid is a hierarchy of meshes that begins with a d-cube at level k = 0, and, for each higher level k > 0, is the result of dividing each cell of level k into two equal children by a hyperplane perpendicular to the coordinate axis (k mod d) [START_REF] Cardoso | Finite elements on dyadic grids with applications[END_REF]. Figure 1 illustrates five steps of the refinement process for d = 3. In practice, one uses only finite segments of this grid, where the subdivision stops at a maximum level. In a regular dyadic grid, the refinement stops at the same level everywhere. In an irregular grid, the maximum level varies from place to place. The topology of a dyadic grid can be represented by a 0-2 binary tree. This is a data structure consisting of a set of elements named nodes, among which there is a special node r, the root; every node has either zero or two children nodes; and every node, except the root, has exactly one parent node. A node that has no children is called a leaf node. The children of a non-leaf node t are called the left child t ℓ and the right child t r . Each node of this tree represents a cell that appeared at some level of the subdivision; the leaf nodes represent the cells that weren't divided. By convention, the left child t ℓ of a non-leaf node t in level k represents the "lower" half c ℓ of the cell c represented by t; that is, the half whose projection on the axis i = k mod d has smallest i-coordinates.

Multiresolution analysis

In mutiresolution analysis, signals can be represented in two ways, as ordinary samples at each scale, or as differences between two consecutive scales. Connecting these two views are the prediction and the restriction operators. The prediction operator P k+1 k takes information from a coarse level k and gives an estimate for the information at the next finer level k + 1. Conversely, the restriction operator P k k+1 takes information from a fine level k + 1 and gives an estimate of the information at a coarser level k. In this paper, the samples of a d-dimensional signal f are averages computed over the cells of a d-dimensional dyadic grid. That is, the sample associated with a cell c in level k of the grid is

f k c = 1 |c| c f (x)dx, (1)
where |c| is the volume of c. The restriction operation is therefore (trivially and exactly) the sum of the averages in the children cells,

f k c = 1 2 f k+1 c ℓ + f k+1 cr . (2)
In the other direction, we predict the cell average of a child cell c r or c ℓ by the formulas

f k+1 cr ≈ f k+1 cr = f k c + 1 8 f k c + -f k c - (3)
f k+1 c ℓ ≈ f k+1 c ℓ = f k c - 1 8 f k c + -f k c - (4)
where c -and c + are the two closest neighbor cells of c at level k in the direction of refinement. See Figure 2. These estimators are exact for quadratic polynomials.

Detail coefficients. In the structure we do not store the averages ( f k c or f k c ), but only the details or wavelet coeficients. Each detail d k c is the difference between the exact average in the cell c and the value predicted for it by formulas (3) and ( 4) from the cell's parent and its neighbors:

d k+1 c = f k+1 c -f k+1 c . (5)
Note that the detail of the root cell is not defined.

Analysis and synthesis. The analysis algorithm computes the details of every cell, given the average values f k c for every cell c. It scans the tree bottom-up, level by level.

For each non-leaf cell c in level k, it executes

δ ← 1 2 f k+1 cr -f k+1 c ℓ ; δ ← 1 8 f k c + -f k c -; δ ← δ - δ d k cr ← +δ; d k c ℓ ← -δ. (6)
Once the detail d k c of a cell has been computed, its average f k c is no longer needed, so we may store the detail in its place. In the root node r, however, we must still keep the average f 0 r of the function over the whole domain. The inverse of the analysis algorithm is the syntesis algorithm, which recomputes the averages f k c from the details. It scans the tree top down, level by level. At each cell c in level k, it executes Compact representation. These algorithms show that knowledge of the cell averages for all leaves is equivalent to knowledge of the average value f 0 r for the root cell together with the detail of every right child cell. To save space, we could store the detail of the right child in its parent's node (and keep the domain average f 0 r in variable external to the tree). Then the leaf nodes would carry no information, and could be omitted from the structure. We will refer to this variant (which is an ordinary binary tree) as the compact tree representation.

δ ← 1 8 f k c + -f k c -; δ ← δ -d k+1 cr ; f k+1 cr = f k c + δ f k+1 c ℓ = f k c -δ. (7

Adaptive resolution grid.

As in any wavelet representation, we can save space and processing time by pruning all sub-trees which do not contribute significantly to the reconstructed signal. If we start with a tree of sufficient depth, we can eliminate all sibling leaf nodes c ℓ and c r such that d k c falls below a prescribed tolerance ǫ k . This condition implies that the predictions f k+1 c ℓ and f k+1 cr will be very close to the actual averages f k+1 c ℓ and f k+1 cr . Here we use Harten's thresholds [START_REF] Harten | Multiresolution representation of cellaveraged data[END_REF],

ǫ k = (1 -q)q (L-k) ǫ, ( 8
)
where q and ǫ are specified by the user, with ǫ > 0 and 0 < q < 1, and L is the maximum level of the initial tree.

Numerical results

In order to compare the efficiencies of dyadic grids and quad-grids, we performed the multiresolution analyses of two different examples in 2D, using cell-average discretization. In all tests, the root cell was the rectangle

[0, 1] × [0, √ 2
2 ], and the starting tree was a uniform grid with 2 10 × 2 10 = 2 20 = 1, 048, 576 leaf cells. This corresponds to tree structures with L = 20 and L = 10 levels for dyadic grid and quad-grid frameworks, respectively. The cell averages f L c were computed for every leaf cell c by Gaussian quadrature with 5 × 5 sampling points. The trees were pruned as described in the previous section, with threshold parameters ǫ = 0.1 and the q = 0.5. The number of non-leaf nodes in the initial tree was 19 i=0 2 i = 1, 048, 575 for the dyadic grid, and 9 i=0 4 i = 349, 525 for the quad-grid. In the first test, we used the signals f (x, y) = 1-tanh(100(x-0.2-t)+0.001(y -1)), (9) for t varying from 0 to 0.6 in steps of 0.1. Equation (9) describes a 2D smooth step function with an almost vertical straight front, moving form left to right. Figure 3 shows the dyadic grid and the corresponding tree at t = 0.1, after pruning cells with small details. Figure 4 shows the corresponding quad-grid and quad-tree. Figure 5 shows the number of leaf cells in both grids for each time step, as a percentage of the number of leaves in the uniform grid. For the second test, we used the signals f (x, y) = 1 if (x -0.5) 2 + (y -0.35) 2 < t, 0 otherwise. (10) for t varying between 0.05 and 0.35 in steps of 0.05. Equation (10) describes a step function with a sharp circular front, expanding from the center of the domain. Figure 6 shows the dyadic grid and its tree at t = 0.2, and Figure 7 shows the corresponding quad-grid and its quad-tree. The number of leaves is plotted in Figure 8.

Space efficiency.

If leaves are explicitly represented in the tree structure, and all nodes have the same fields, then the space E used by the structure is E = (pA + B)n, where n is the number of nodes, p is the number of pointers in each node, A is the size of a pointer in bytes, and B is the size of any additional information stored in each node (such as the detail coefficients d k c ). In all these trees we have n = (pm -1)/(p -1) ≈ mp/(p -1), where m is the number of leaf nodes. From the plots in Figure 5, we see that, in the first test, the quad-grid (p = 4) had about 8 times as many leaf cells as the dyadic grid (p = 2), and therefore about 5 times as many tree nodes, for the same accuracy. Assuming A = 4 and B = 8 bytes, we conclude that the quad-tree used 5(24/16) ≈ 7.5 times as much storage as the dyadic grid. In the second test, the quad-grid had about 1.32 times as many leaf cells as the dyadic grid, and therefore about 0.88 as many tree nodes. With the same A and B, the quad grid still used 0.88(24/16) ≈ 1.32 times as much space as the dyadic grid. Had we used the compact representation of the tree, with omitted leaves, the storage cost would be E = (pA + (p -1)B)(n -m). The quad-tree would use 7.5 times as much storage as the dyadic tree in the first example, and 1.1 times as much in the second example.

Conclusions

Our tests show that adaptive dyadic grids are substantially more efficient than quad-grids for the same level of accuracy, both in terms of space needed to store the topology (tree structure) of the grid, and in the number of leaf cells retained -which determines the time cost of most adaptive numeric algorithms.

Figure 1 :

 1 Figure 1: 3D dyadic grids.

Figure 2 :

 2 Figure 2: Definition of c -, c + , c, c r .

)

  After this step, the details d k+1 cr and d k+1 c ℓ of the children are no longer needed, and can be overwritten with the reconstructed averages f k+1 cr and f k+1 c ℓ .

Figure 3 :

 3 Figure 3: Pruned dyadic tree (top) and dyadic grid (bottom) for the first signal at t = 0.1.

Figure 4 :

 4 Figure 4: Pruned quad-tree (top) and quad-grid (bottom) for the first signal at t = 0.1..

Figure 5 :

 5 Figure 5: Leaf count in the pruned trees for the first test..

Figure 6 :

 6 Figure 6: Pruned dyadic tree (top) and dyadic grid (bottom) for the second signal at t = 0.2..

Figure 7 :Figure 8 :

 78 Figure 7: Pruned quad-tree (top) and quad-grid (bottom) for the second signal at t = 0.2..

Acknowledgments

The authors thank CNPq (grants 06631/07-5, 472402/07-2, and 142191/06-0) and FAPESP (07/52015-0) for financial support.


Stephen D Casey
email: scasey@american.edu

Brian M Sadler
email: bsadler@arl.army.mil

Adaptive and Ultra-Wideband Sampling via Signal Segmentation and Projection

Adaptive frequency band (AFB) and ultra-wide-band (UWB) systems require either rapidly changing or very high sampling rates. Conventional analog-to-digital devices have non-adaptive and limited dynamic range. We investigate AFB and UWB sampling via a basis projection method. The method decomposes the signal into a basis over time segments via a continuous-time inner product operation and then samples the basis coefficients in parallel. The signal may then be reconstructed from the basis coefficients to recover the signal in the time domain. We develop the procedure of this method, analyze various methods for signal segmentation and close by creating systems designed for binary signals.

Introduction

Adaptive frequency band (AFB) and ultra-wide-band (UWB) systems, requiring either rapidly changing or very high sampling rates, stress classical sampling approaches. At UWB rates, conventional analog-to-digital devices have limited dynamic range and exhibit undesired nonlinear effects such as timing jitter. Increased sampling speed leads to less accurate devices that have lower precision in numerical representation. This motivates alternative sampling schemes that use mixed-signal approaches, coupling analog processing with parallel sampling, to provide improved sampling accuracy and parallel data streams amenable to lower speed (parallel) digital computation. We investigate AFB and UWB sampling via a basis projection method. The method was introduced as a means of UWB parallel sampling by Hoyos et. al. [START_REF] Hoyos | Ultra wideband analog-to-digital conversion via signal expansion[END_REF] and applied to UWB communications systems [START_REF] Hoyos | Broadband multicarrier communication receiver based on analog to digital conversion in the frequency domain[END_REF][START_REF] Hoyos | Frequency domain implementation of the transmitted-reference ultrawideband receiver[END_REF][START_REF] Hoyos | UWB mixed-signal transform-domain direct-sequence receiver[END_REF]. The method first decomposes the signal into a basis over time segments via a continuous-time inner product operation and then samples the basis coefficients in parallel. The signal may then be reconstructed from the basis coefficients to recover time domain samples, or further processing may be carried out in the new domain [START_REF] Hoyos | Ultra wideband analog-to-digital conversion via signal expansion[END_REF]. We address several issues associated with the basisexpansion and sampling procedure, including choice of basis, truncation error, rate of convergence and segmentation of the signal. We develop a mathematical model of the procedure, using both standard (sine, cosine) basis elements and general basis elements, and give this rep-resentation in both the time and frequency domains. We compute exact truncation error bounds, and compare the method with traditional sampling. We close by developing the method for binary signals.

Sampling via Projection

Let f be a signal of finite energy whose Fourier transform

f has compact support, i.e., f, f ∈ L 2 , with supp( f ) ⊂ [-Ω, Ω].
The signal is in the Paley-Wiener class P W (Ω). For a block of time T c , let

f (t) = k∈Z f (t) χ [(k)Tc,(k+1)Tc] (t) .
For this original development, we keep T c fixed. We later let T c be adaptive and will denote the adaptive time segmentation as τ c (t). A given block f k (t) = f (t) χ [(k)Tc,(k+1)Tc] (t) can be T cperiodically continued, getting

(f k ) • (t) = (f (t) χ [(k)Tc,(k+1)Tc] (t)) • .
Expanding (f k ) • (t) in a Fourier series, we get Tc) , where

(f k ) • (t) = n∈Z (f k ) • [n]e (2πint/
(f k ) • [n] = 1 T c (k+1)Tc (k) Tc f (t)e (-2πint/Tc) dt .
Given that the original function f is Ω band-limited, we can estimate the value of n for which

f k [n] is non-zero. At minimum, f k [n] is non-zero if n T c ≤ Ω , or equivalently, n ≤ T c • Ω . Let N = ⌈T c • Ω⌉ .
(Note that the truncated block functionsf k are not bandlimited. We discuss this in section 3.) For this choice of N , we compute

f (t) = k∈Z f (t) χ [(k)Tc,(k+1)Tc] (t) = k∈Z (f k ) • (t) χ [(k)Tc,(k+1)Tc] (t) ≈ k∈Z n=N n=-N (f k ) • [n]e (2πint/Tc) χ [(k)Tc,(k+1)Tc] (t) .
Given this choice of the standard (sines, cosines) basis, we can, for a fixed value of N , adjust to a large bandwidth Ω by choosing small time blocks T c . Also, after a given set of time blocks, we can deal with a increase or decrease in bandwidth Ω by again adjusting the time blocks, e.g., given an increase in Ω, decrease the time blocks adaptively to τ c (t), and vice versa. There is, of course, a price to be paid. The quality of the signal, as expressed in the accuracy the representation of f , depends on N , Ω and T c .

Theorem : [The Projection Formula] Let f , f ∈ L 2 (R) and f ∈ P W Ω , i.e. supp( f ) ⊂ [-Ω, Ω]. Let T c be a fixed block of time. Then, for N = ⌈T c • Ω⌉, f (t) ≈ f P (t), where

f P (t) = k∈Z N n=-N f k [n]e (2πint/Tc) χ [kTc,(k+1)Tc] (t). (1)
The Projection Method can adapt to changes in the signal. Suppose that the signal f (t) has a band-limit Ω(t) which changes with time. For example, let f be a signal from a cell phone which changes from voice to a highly detailed musical piece. This change effects the time blocking τ c (t) and the number of basis elements N (t). This, of course, makes the analysis more complicated, but is at the heart of the advantage the Projection Method has over conventional methods.

During a given τ c (t), let

Ω(t) = sup {Ω(t) : t ∈ τ c (t)}.
For a signal f that is Ω(t) band-limited, we can estimate the value of n for which

f k [n] is non-zero. At minimum, f k [n] is non-zero if n τ c (t) ≤ Ω(t) , or equivalently, n ≤ τ c (t) • Ω(t) . Let N (t) = ⌈τ c (t) • Ω(t)⌉ .
For this choice of N (t), we have the following.

Theorem : [The Adaptive Projection Formula] Let f , f ∈ L 2 (R) and f have a variable but bounded bandlimit Ω(t). Let τ c (t) be an adaptive block of time and given τ c (t), let

Ω(t) = sup {Ω(t) : t ∈ τ c (t)}. Then, for N (t) = ⌈τ c (t) • Ω(t)⌉ , f (t) ≈ f P (t),
where

f P (t) = k∈Z N (t) n=-N (t) f k [n]e (2πint/τc) χ [kτc,(k+1)τc] (t). (2)
In comparison, Shannon Sampling examines the function at specific points, then uses those individual points to recreate the signal. The Projection Method breaks the signal into segments in the time domain and then approximates their respective periodic expansions with a Fourier series. This process allows the system to individually evaluate each piece and base its calculation on the needed bandwidth. The individual Fourier series are then summed, recreating a close approximation of the original signal. It is important to note that instead of fixing T c , the method allows us to fix any of the three while allowing the other two to fluctuate. The easiest and most practical parameter from the design factor to fix is N . For situations in which the bandwidth does not need flexibility, it is possible to fix Ω and T c by the equation N = ⌈T c • Ω⌉. However, if greater bandwidth Ω is need, choose shorter time blocks T c . The Projection Method adapts to general orthonormal systems, much as Kramer-Weiss extends sampling to general orthonormal bases. Given a function f such that f ∈ P W Ω , let T c be a fixed time block. Define f (t), f k (t) and f k • (t) as in the beginning of the computation above. Now, let {ϕ n } be a general orthonormal system for L 2 [0, T c ]. Then,

f k • (t) = ∞ n=-∞ f k [n]ϕ n (t), where f k [n] = f k • , ϕ n . Since f ∈ P W Ω , there exists N = N (T c , Ω) such that f k [n] = 0 for all n > N . Therefore, f (t) ≈ f P (t),
where

f P (t) = ∞ k=-∞ N n=-N f k [n]ϕ n (t) χ [kTc,(k+1)Tc] (t).
(3) Given characteristics of the input class signals, the choice of basis functions used in the the Projection Method can be tailored to optimal representation of the signal or a desired characteristic in the signal. We develop a Walsh system for binary signals in section 4. We close this section with a different system of segmentation for the time domain. This was created because it is relatively easy to implement, cuts down on frequency error and has no loss of data in time. It The Trap function has perfect overlay in the time domain and 1/ω 2 decay in frequency space. When one time block is ramping down, the adjacent block is ramping up at exactly the same rate. This leads to the Projection formula

k∈Z N n=-N ((f •Trap) k [n]e (2πint/(Tc+r)) Trap(t-k(T c /2)) .

Error Analysis

To compute truncation error, we first calculate the Fourier transform of both sides of the equation. Let f ∈ P W (Ω), so f ∈ L 2 and Ω band-limited. For N = ⌈T c • Ω⌉,

f P (t) = k∈Z N n=-N f k [n]e (2πint/Tc) χ [kTc,(k+1)Tc] (t)
Taking the transform of both sides and evoking the relationship between the transform and convolution gives

f P (ω) = k∈Z N n=-N f k [n] e (2πint/Tc) (ω) * χ [kTc,(k+1)Tc] (t) (ω)
Performing the indicated transforms using the definition results in

f P (ω) = k∈Z N n=-N f k [n] δ(ω - n T c ) * e (2πi(k-1 2 )Tcω) sin(πT c ω) πω
It is important to note that f • χ [kTc,(k+1)Tc] is no longer band-limited, but it does decay at a rate less than or equal to 1 ω in frequency. Using the relationship between translation and modulation, we get the following. Theorem : [The Fourier Transform of the Projection Formula] Let f , f ∈ L 2 (R) and f ∈ P W Ω , i.e. supp( f ) ⊂ [-Ω, Ω]. Let T c be a fixed block of time. Then, for N = ⌈T c • Ω⌉,

f P (ω) = ∞ k=-∞ N n=-N f k [n]e (2πi(k-1 2 )Tc(ω-n Tc ) sin(π( ωTc 2 -n 2 )) π(ω -n Tc ) (4)
The system using overlapping Trap functions has the advantage of 1/ω 2 decay in frequency. Let β L = T c /(4r) + r, α L = T c /(4r) + r/2, β S = T c /(4r) + r -1, α S = T c /(4r) -r/2. The Fourier transform of Trap is

(β L ) sin(2πα L (ω) π(ω) 2 -(β S ) sin(2πα S (ω) π(ω) 2 .
This replaces the sinc term in the equation above. The Fourier coefficients are also different, and are computed in the same method as the de la Vallée-Poussin kernel used in Fourier series.

In the formula for the Projection Method, there is a reliance on a number N , representative of the number of Fourier series components. In order to ensure maximum utility from the formula, the difference between the infinitely summed series and the truncated must be made a minimum. To do this, the mean square error must be calculated. We compute this as a truncation error on the number of Fourier coefficients used to represent a given block f k . For a fixed N , the mean square error is

e 2 N = f k -f k,N 2 2 = f k -f k,N 2
2 . Computing and then simplifying gives

e 2 N = 1 T c (k+1)Tc kT C |f k • (t) - |n|≤N f k [n]e (2πitn/Tc) | 2 dt = 1 T c (k+1)Tc kT C | |n|>N f k [n]e (2πitn/Tc) | 2 dt .
Applying the triangle inequality to the right side and then exploiting the fact that e (2πitn/Tc) is an orthonormal system, thus |e (2πitn/Tc) | = 1, we arrive at the following:

e 2 N = 1 T c (k+1)Tc kT C | |n|>N f k [n]e (2πitn/Tc) | 2 dt (5) ≤ |n|>N |f k [n]| 2 • 1 T c (k+1)Tc kTc 1 2 dt = |n|>N |f k [n]| 2
This demonstrates that the value of N has to be chosen carefully. This truncation error perpetuates over all the blocks. The Projection Method experiences error due to truncation in two separate categories: time and frequency. The error in frequency is a function of the errors on each block due to the choice of N . By duality, this gives us errors in time.

We can also get an error in time by loss of a given block or blocks of information. This is easier to compute. Given any lost or partially transmitted block f k,L , error is simply

f k -f k,L 2 .
Error over the entire signal is computed by simply adding up the blocks. Cell phone users are used to lost information blocks, which gives rise to the following frequently used phrase -"Can you hear me now?"

Binary Signals

The Walsh functions {ω n } form an orthonormal basis for L 2 [0, 1]. The basis functions have the range {1, -1}, with values determined by a dyadic decomposition of the interval. The Walsh functions are of modulus 1 everywhere. The functions are give by the rows of the unnormalized Hadamard matrices, which are generated recursively by

H(2) = 1 1 1 -1 H(2 (k+1) ) = H(2) ⊗ H(2 k ) = H(2 k ) H(2 k ) H(2 k ) -H(2 k ) .
We point out that although the rows of the Hadamard matrices give the Walsh functions, the elements have to be reordered into sequency order. Walsh arranged the components in ascending order of zero crossings (see [START_REF] Beauchamp | Applications of Walsh and Related Functions[END_REF]). The Walsh functions can also be interpreted as the characters of the group G of sequences over Z 2 , i.e., G = (Z 2 ) N . The Walsh basis is a well-developed system for the study of a wide variety of signals, including binary. The Projection Method works with the Walsh system to create a wavelet-like system to do signal analysis. First assume that the time domain is covered by a uniform block tiling χ [kTc,(k+1)Tc] (t). Translate and scale the function on this kth interval back to [0, 1] by a linear mapping. Denote the resultant mapping as f k , which is an element of L 2 [0, 1]. Given that f ∈ P W (Ω), there exists an N > 0 (N = N (Ω)) such that f k , ω n = 0 for all n > N . The decomposition of f k into Walsh basis elements is

N n=0 f k , ω n ω n .
Translating and summing up gives the Projection repre-

sentation f P f P (t) = k∈Z N n=0 f k , ω n ω n χ [kTc,(k+1)Tc] (t). (6)
Next assume that the time domain is covered by a uniform overlapping trapezoidal tiling Trap(t -k(T c /2)). Note that the construction of the trapezoidal system results in the loss of no signal data, for just as a given block is ramping down, the subsequent block is ramping up at exactly the same rate. Again translate and scale the function on this kth interval back to [0, 1] by a linear mapping. Denote the resultant mapping as

f k T . The resultant function is an element of L 2 [0, 1]. Given that f ∈ P W (Ω), there exists an M > 0 (M = M (Ω)) such that f k T , ω n = 0 for all n > M . The decomposition of f k T into Walsh basis elements is M n=0 f k , ω n ω n .
Translating and summing up gives the Projection representation

f P T f P T (t) = k∈Z N n=0 f k T , ω n ω n Trap(t-k(T c /2)). (7)

Conclusions

The Projection Method gives a method for analog-todigital encoding which is an alternative to Shannon Sampling. Projection gives a procedure for the sampling of a signal of variable or ultra For fixed N , if greater bandwidth Ω is need, choose shorter time blocks T c . The price paid for this flexibility is in signal error, which has been computed above. The Projection Method can also adapt to changes in the signal, e.g., f (t) has a band-limit Ω(t) which changes with time. This change effects the time blocking τ c (t) and the number of basis elements N (t). During a given τ c (t), let Ω(t) = sup {Ω(t) : t ∈ τ c (t)}. For a signal f that is Ω(t) band-limited, we can estimate the value of n for which

f k [n] is non-zero. At minimum, f k [n] is non-zero if n τ c (t)
≤ Ω(t) , or equivalently, n ≤ τ c (t) • Ω(t) .

We let N (t) = ⌈τ c (t) • Ω(t)⌉ , This adaptable time segmentation makes the analysis more complicated, but is at the heart of the advantage the Projection Method has over conventional methods. Subsequent work on this method will focus on minimizing error, creating systems based on the Projection Method tailored to different types of signals and optimizing signal reconstruction in a noisy environment.

  was developed by studying the de la Vallée-Poussin kernel used in Fourier series. Let 0 < r < T c /2 and let Tri L (t) = max{[((T c /(4r)) + r) -|t|/(2r)], 0} , Tri S (t) = max{[((T c /(4r)) + r -1) -|t|/(2r)], 0} and Trap(t) = Tri L (t) -Tri S (t) .

  -wide bandwidth Ω by varying the time blocks T c . If f is Ω band-limited, we can estimate the value of n for which the Fourier coefficientsf k [n] of a given time block are non-zero. At minimum, f k [n] is non-zero if n Tc ≤ Ω, or equivalently, n ≤ T c • Ω. If N = ⌈T c • Ω⌉, then, f (t) ≈ f P (t), where f P (t) = k∈Z N n=-N f k [n]e (2πint/Tc) χ [kTc,(k+1)Tc] (t).

  f k [n]e (2πint/τc) χ [kτc,(k+1)τc] (t).