Timekeeping and related functions such as navigation are important in distributed systems with manufactured nodes such as satellites, spacecraft, distributed computing, and communications. With increases in frequencies, velocities, clock rates, and bit rates, as well as the tightening timekeeping and positioning accuracy demanded of applications, relativistic effects increasingly enter as a design consideration. In this paper, representative applications are surveyed to illustrate relativistic effects in timekeeping. The general theory of relativity is avoided by neglecting gravity in the presence of motion and neglecting motion in the presence of gravity. The special theory of relativity combined with the equivalence principle then provide closed-form models that aid system designers in understanding the nature and relevance of relativistic effects. This is applied to modeling relativistic clock rate and time synchronization in the presence of motion or gravity. The kinematics of special relativity is developed using a new simplified approach in which velocity and acceleration are referenced to the frame-invariant proper time rather than the conventional frame-dependent coordinate time. This approach considerably narrows the scope of relativistic effects, and is particularly appropriate for manufactured systems. Further, by decomposing acceleration into components longitudinal and transverse relative to the direction of motion, simple scalar frame-invariant relations between proper and coordinate perspectives follow. The dynamics and conservation laws of special relativity are illustrated by the relativistic rocket equation. Finally, the Lorentz transformation and its implications are derived from first principles, completing a self-contained exposition. Our perspective and approaches are tailored to the needs of engineering practitioners, educators, and students, and our new methodology may be appropriate in an introductory physics education as well. Mathematically the treatment is based on first-order vector differential equations and the chain rule of differentiation.

The germ of the component idea arose in mass production as the interchangeable part, but in today's information and communications technology (ICT) industries the component can connote considerably more, such as multiple uses, opportunistic combinations with other components, design by assembly, and incremental evolution through field replacement with upgraded components. In spite of its many advantages, the component has failed to keep up with increasing scales of integration, increasing use of software, and the resulting complexity and application diversity. A rethinking of the component and associated industry practices is needed in light of modern technology and applications. Componentization has many payoffs, including as a process for industry coordination, most notably in large multivendor complex systems with fragmented administrative and ownership domains. Invigorating componentization requires abandoning antiquated concepts such as components are exclusively hardware or software or even exclusively technological, are units of manufacture and packaging, or that each component is the responsibility of an individual firm. The system component, which incorporates hardware, software, and oftentimes even human process or organizational elements, whatever is necessary to achieve a coherent body of functionality, is the appropriate perspective today.

Multimedia traffic sources with tight latency constraint, arising in sessions such as data query, image and video transmissions, can be very bursty and are inefficient to be serviced with a dedicated high-speed link. On wireline networks, bursty traffic is statistically multiplexed to fully utilize the link capacity. In light of recent proposals for wideband CDMA (WCDMA) to service multimedia data, there is a similar need to develop wireless network architectures with flexible bandwidth allocation to facilitate statistical multiplexing. To address this issue, we compared the throughput performance of two promising WCDMA configurations, high speed CDMA (HS-CDMA) and multi-code CDMA (MC-CDMA). HS-CDMA assigns each user a single code with small spreading gain to enable a high transmission rate when it is needed. In contrast, MC-CDMA employs codes with a large spreading gain but permits a user to acquire more than one code. As expected, the throughput of a configuration depends on the receiver structure as well as the operation scenarios like power and SNR constraints. When matched filter receivers are applied, HS-CDMA fares better in most occasions. When multi-user receivers are used, both configurations deliver the same throughput except the situation when the total power is bounded.

In his 1962 paper "A Day in the Life of a Student in 2012", Ponte describes the university of 2012 through the eyes of a student. Such a paper may be written to predict the future, to influence changes, or simply to highlight shortcomings and opportunities in the present. His motivation seems to be prediction, so it is best to view the paper in that light. Ponte's prophecy still has over a decade to play out. One vision not yet true, but likely, is the obsolescence of the lecture hall-his Professor Faraway gives recorded, masterful lectures that are broadcast to students, who gather in teams of 30 around a task master. Indeed, the lecture hall does seem antiquated today-it may be replaced by a learning hall, where faculty and students gather physically to engage in a discussion and projects, supplemented by a multimedia textbook, which students use to self study. One-way lectures can be satisfactorily replaced by store and playback, with a substantial improvement in productivity, but what cannot be readily displaced is an intellectual give-and-take discussion among faculty and students, accompanied by friendship and community building. Thus, Ponte's task masters and closely knit group projects seem likely to arise together with multimedia study materials. We now offer a new essay in the spirit of his. Our objective is not so much prediction, but rather to speak to our own era, using a speculative view of the future to point out today's shortcomings and opportunities. Like Ponte, our essay reflects both our hopes and our fears for the future. Reflecting the greater pace of change today, this vision is a more radical departure than Ponte's. Fifty years from now, this essay will probably be only mildly amusing, since the details of our prediction are unlikely to reflect reality. A more realistic goal is to influence the course of education today.

Timing skew has been the major limitation for high-speed synchronous operation of a VLSI system. In this paper, a statistical timing model that accounts for both static and random timing skew is proposed. Based on this model, we analyze the timing rules of a synchronous VLSI system consisting of multiple pipelined stages, establish the yield of the system as a function of its device characteristics, and derive the relationship between the maximum throughput of such a system and its timing skew. The following timing schemes are evaluated: conventional pipelining, in which the transmitter cannot initiate the next cycle until the receiver has received the data and wave pipelining, in which the transmitter initiates the next cycle as soon as the current data has been sent out. The results show that the yield of a VLSI system using either of the pipelining schemes exhibits threshold behavior for Gaussian distributed static skew. Furthermore, the system throughput is shown to be very sensitive to the random skew.

Digital video coding has traditionally used frame-by-frame synchronous reconstruction. The transport must then be delay-jitter-free, forcing the modern integrated service packet network such as the Internet to operate in an inefficient "circuit emulation" mode. This mode results in a jitter-free delay representative of the worst-case network delay, which is problematic for delay-sensitive interactive applications. In response, we have proposed and demonstrated a "delay cognizant" model of video coding (DCVC) that operates in an asynchronous reconstruction mode. DCVC minimizes the perceptual delay observed by the user, and still achieves good quality and high compression. Furthermore, the feasibility of asynchronous reconstruction is evidenced by vision science studies of spatiotemporal masking in human visual systems at the temporal edges of video.

We are developing a sophomore course to serve as a first course in electrical engineering. The course focuses on discrete-time systems. Its goal is to give students an intuitive understanding of concepts such as sinusoids, frequency domain, sampling, aliasing, and quantization. In the laboratory, students build simulations and real-time systems to test these ideas. By using a combination of high-level and DSP assembly languages, the students experiment with a variety of views into the representation, design, and implementation of systems. The students are exposed to a digital style of implementation based on programming both desktop and embedded processors.

Much research and development related to digital video has targeted storage, wired backbone, and broadcast wireless transport environments. We address video transport in a heterogeneous network, especially with interference- and fading dominated wireless access, such as a cellular local-area or wide-area network. It is expected that multimedia (including video) will be an important application for desktop computers, and this suggests offering similar wireless capabilities. We note a number of deficiencies in existing video compression standards such as MPEG for this environment, and identify a number of challenging new research issues.

As has been widely recognized for some time, the computing and telecommunications technologies are converging. This has meant different things at different times. In this review paper, we describe the current stare of convergence, and speculate about what it may mean in coming years. In particular, we argue that as a result of the horizontal integration of all media (voice, audio, video, animation, data) in a common network and terminal infrastructure, telecommunications and networked-computing applications are no longer distinguishable. Considering that the old terminology is no longer meaningful, we attempt to codify networked applications in accordance with their functionality and immediacy. As application functionality is increasingly defined in software, with commensurate cost-effective programmable terminals and means for distribution of applications over the network itself, we argue that user-to-user applications will be greatly impacted, moving into the rapid-innovation regime that has characterized user-to-information-server applications in the recent past. Finally we identify a number of areas where different technical approaches and design philosophies have characterized telecommunications and computing, and discuss how these technical approaches are merging and identify areas of needed research. We do not address complementary forms of convergence at the application or industrial level, such as convergence of the information and content-provider industries, but rather restrict attention to the infrastructure and technology.

Many communications applications require similar processing functionality but are implemented independently. In particular, a number of applications (including trellis coding, encryption, and speech recognition) use techniques based on shortest path search algorithms. In this paper, we propose a high-throughput architecture that can search for the shortest path within a graph. The architecture can decode any data encoded with a finite state machine (FSM) or data encrypted in a dynamic trellis code and also serve as a specialized processor for other searching and matching applications. Balance between flexibility and hardware efficiency is achieved by an integrated design of architecture, in-place scheduling, and concurrent algorithms.

We consider the capacity C of a continuous-time channel with frequency response H(f) and additive white Gaussian noise. If H(f)|/sup -2/ behaves like a polynomial of order /spl rho/ at high frequencies, we show that the per-symbol capacity approaches /spl rho//2 nats per channel use at high signal powers. If the receiver uses an ideal zero forcing decision-feedback equalizer (DFE) consisting of a sampled whitened-matched filter followed by a zero-forcing tail canceler that is free of error propagation, the overall system is free of intersymbol interference and has a well-defined capacity C/sub ZF/. By comparing this capacity with the capacity C of the underlying channel, we quantify the loss of information inherent in the tail-canceling operation that typifies zero-forcing DFE and zero-forcing precoding systems. For strictly bandlimited channels, we find that the capacity penalty approaches zero in the limit of large signal power. On the other hand, for nonstrictly bandlimited channels, the asymptotic penalty is nonzero; however, with bandwidth optimization, the asymptotic penalty is at most 0.59 dB, and the asymptotic ratio C/sub ZF//C is at least 93.6%, depending on the asymptotic order /spl rho/ of the channel response.

Many advanced video applications require manipulations of compressed video signals. Popular video manipulation functions include overlap (opaque or semitransparent), translation, scaling, linear filtering, rotation, and pixel multiplication. We propose algorithms to manipulate compressed video in the compressed domain. Specifically, we focus on compression algorithms using the discrete cosine transform (DCT) with or without motion compensation (MC). Such compression systems include JPEG, motion JPEG, MPEG, and H.261. We derive a complete set of algorithms for all aforementioned manipulation functions in the transform domain, in which video signals are represented by quantized transform coefficients. Due to a much lower data rate and the elimination of decompression/compression conversion, the transform-domain approach has great potential in reducing the computational complexity. The actual computational speedup depends on the specific manipulation functions and the compression characteristics of the input video, such as the compression rate and the nonzero motion vector percentage. The proposed techniques can be applied to general orthogonal transforms, such as the discrete trigonometric transform. For compression systems incorporating MC (such as MPEG), we propose a new decoding algorithm to reconstruct the video in the transform domain and then perform the desired manipulations in the transform domain. The same technique can be applied to efficient video transcoding (e.g., from MPEG to JPEG) with minimal decoding.>

The finite element method is a general and powerful technique for solving partial differential equations. The computationally intensive step of this technique is the solution of a linear system of equations. Very large and very sparse system matrices result from large finite-element applications. The sparsity must be exploited for efficient use of memory and computational components in executing the solution step. In this paper we propose a scheme, called SPAR, for efficiently storing and performing computations on sparse matrices. SPAR consists of an alternate method of representing sparse matrices and an architecture that efficiently executes computations on the proposed data structure. The SPAR architecture has not been built, but we have constructed a register-transfer level simulator and executed the sparse matrix computations used with some large finite element applications. The simulation results demonstrate a 95% utilization of the floating-point units for some 3D applications. SPAR achieves high utilization of memory, memory bandwidth, and floating-point units when executing sparse matrix computations.>

We consider parameter estimation for a FIFO queue with deterministic service times and two independent arrival streams of "observed" and "unobserved" packets. The arrivals of unobserved packets are Poisson with an unknown rate /spl lambda/ while the arrivals of observed packets are arbitrary. Maximum likelihood estimation of /spl lambda/ is formulated based on the arrival times and waiting times of k observed packets. The likelihood function is derived in terms of the transition probabilities of the unfinished work process which are calculated recursively. Sufficient conditions for consistency, asymptotic normality, and asymptotic efficiency are given. The mean and variance of the MLE are measured in simulation experiments. Numerical results indicate that the MLE is consistent and asymptotically normal.>

Article Transform coding of arbitrarily-shaped image segments Share on Authors: Shih Fu Chang View Profile , David G. Messerschmitt View Profile Authors Info & Claims MULTIMEDIA '93: Proceedings of the first ACM international conference on MultimediaSeptember 1993 Pages 83–90https://doi.org/10.1145/166266.166275Published:01 September 1993 23citation664DownloadsMetricsTotal Citations23Total Downloads664Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A recursive method for evaluating the impulse response of an indoor free-space optical channel with Lambertian reflectors is presented. The method, which accounts for multiple reflections of any order, enables accurate analysis of the effects of multipath dispersion on high-speed indoor optical communication systems. A simple algorithm for computer implementation of the technique and computer simulation results for both line-of-sight and diffuse transmitter configurations are also presented. In both cases, it is shown that reflections of multiple order are a significant source of intersymbol interference. Experimental measurements of optical multipath, which help verify the accuracy of the simulations, are discussed.>

The parallel Viterbi decoding is discussed for two different cases: uncontrollable sources and controllable sources. For general, uncontrollable Markov processes, a previously known parallel method is extended to a hierarchical parallel decoding approach, which achieves a lower latency. For controllable Markov sources in telecommunications applications, new parallel decoding methods are obtained by controlling the source processes in appropriate ways. The focus is on the parallel decoding methods for controllable sources because these methods have zero processing overhead. Because the methods modify the coding process, they bring positive changes to framing and negative changes to latency and code performance. However, one can adjust the parameters of the methods to make the degradation negligible. Because of their low overhead, the methods are most attractive for high-speed decoders for convolutional and trellis codes, and they are also applicable to other sequential algorithms for suboptimal decoding and estimation of complex Markov sources.>

A new method of implementing an asynchronous adaptive fractionally spaced equalizer is presented for use in voiceband data modems. The method uses finite impulse response (FIR) approximations to interpolation filters to modify equalizer coefficients and a digital phase-locked loop for timing recovery. The method allows for echo cancellation and equalization to be conducted synchronously, simplifying hardware and eliminating the need to recover and resample a continuous-time far-end signal. The penalty imposed is a slightly higher amount of computation for interpolation. It is shown that the interpolation can be done with fixed three-tap FIR filters.>

Techniques for resynchronizing motion-compensation-based coders and strategies for the recovery of lost motion vectors are discussed. Leaky-difference resynchronization yields perceptually pleasing video sequences even at fairly high cell loss rates. Future study is needed to determine optimal data-dependent or network-state-dependent conditional resynchronization strategies. Lost motion vectors can be predicted accurately with either the median of intraframe neighboring vectors or the corresponding past-frame vector. The replacement of lost motion vectors with estimates such as these can significantly improve the quality of video affected by cell loss.>

A high-throughput architecture that can search for the shortest path within a graph is proposed. The architecture can decode any data encoded with a finite state machine or data encrypted in a dynamic trellis code, and also serve as a specialized processor for other searching and matching applications. The proposed retargetable architecture is suitable for futuristic workstations equipped with wireless access, basic voice recognition, and high speed data services. Balance between flexibility and hardware efficiency is achieved by an integrated design of architecture, in-place scheduling, and concurrent algorithms.>

Two classes of architectures-the tree-based and the PLA-based architectures-have been discussed in the literature for the variable length code (VLC) decoder. Pipelined or parallel architectures in these two classes are proposed for high-speed implementation. The pipelined tree-based architectures have the advantages of fully pipelined design, short clock cycle, and partial programmability. They are suitable for concurrent decoding of multiple independent bit streams. The PLA-based architectures have greater flexibility and can take advantages of some high-level optimization techniques. The input/output rate can be fixed or variable to meet the application requirements. As an experiment, the authors have constructed a VLC based on a popular video compression system and compared the architectures. A layout of the major parts and a simulation of the critical path of the pipelined constant-input-rate PLA-based architecture using a high-level synthesis approach estimates that a decoding throughput of 200 Mb/s with a single chip is achievable with CMOS 2.0 mu m technology.>

For pt.I see ibid, vol.2, no.2, p.187, 1992, For applications in graphic computers, image and video composition, high-definition television (HDTV), and optical fiber networks, Huffman-coded images need to be reconstructed at a high throughput rate. Part I showed several architectural and architecture-specific optimization techniques. However, due to the recursion within the reconstruction algorithm, the achievable throughput rate for a given decoding architecture in a given IC technology is limited. The authors propose various concurrent decoding methods to relax the throughput limit by using parallel or pipelined hardware. These methods are simple, effective, flexible, and applicable to general decoder architectures. Unlimited concurrency can be achieved at the expense of additional latency, the overhead is low, and the complexity increases linearly with the throughput improvement. It is believed that the proposed methods and architectures make it possible to reconstruct arbitrarily high resolution Huffman-coded images and video in real time with current electronics.>

The use of two models of computation, synchronous dataflow (SDF) and dynamic dataflow (DDF), to design and implement signal processing applications with multiple sample rates is discussed. The SDF model is used for synchronous applications. SDF is amenable to compile-time scheduling, and hence is much more efficient at runtime. The design environment, Ptolemy, can simultaneously support multiple models of computation, so SDF and DDF can be combined in a single application. Hence, the implementation will incur the run-time cost of DDF only for those asynchronous portions that absolutely must incur such cost. As an illustration, the authors detail a synchronous application, sample-rate conversion using polyphase filters, and an asynchronous application, timing recovery for an amplitude-shift-keyed signal.>

A comparison is made of four modular composition methods suitable for pipeline architectures, including object-based and pel-based composition methods with absolute or relative ordering. For each composition method, it is shown what it does, what it means physically, and thus what limitation it imposes. The conclusion is that the object-based methods, although more efficient to describe video composition, are not completely general. A method is proposed to extend the generality of object-based composition while also retaining its efficiency in describing video composition.>

Many video compression systems require a high-speed implementation of the huffman decoder. The recursive iteration of the decoding process limits the achievable decoding throughput with a given IC technology. Two classes of VLSI architectures for high speed implementation are designed: the tree-based architectures and the programmable logic array (PLA)-based architectures. A variable-length-code based on a popular video compression system is constructed and the pros and cons of each architecture are compared. The major parts of a pipelined constant-input-rate PLA-based architecture using a high-level synthesis approach are simulated. It is claimed that the decoding throughput of 200 Mb/s is achievable with CMOS 2.0 mu m technology.>

Article Three-dimensional finite-element analyses: implications for computer architectures Share on Authors: Valerie E. Taylor Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CAView Profile , Abhiram Ranade Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CAView Profile , David G. Messerschmitt Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CAView Profile Authors Info & Claims Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on SupercomputingAugust 1991 Pages 786–795https://doi.org/10.1145/125826.126188Online:01 August 1991Publication History 0citation278DownloadsMetricsTotal Citations0Total Downloads278Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The authors demonstrate architectural techniques, for small-state feedback circuits that significantly improve the throughput without requiring circuit design efforts or advanced technologies. The method is flexible in terms of achievable implementations and speedups. The authors discuss a new high-throughput solution for systems with finite-level feedback values. As an example, the authors consider coding and signal processing systems for optical communications, which usually have very simple feedback. The authors demonstrate the method by realizing a 2 micron CMOS layout of a bimode 3B4B line coder. Simulation results show that, using standard cell design, the chip achieves a coding rate of 1.4 Gb/s. Other design options are discussed.>

Rate-optimal compile-time multiprocessor scheduling of iterative dataflow programs suitable for real-time signal processing applications is discussed. It is shown that recursions or loops in the programs lead to an inherent lower bound on the achievable iteration period, referred to as the iteration bound. A multiprocessor schedule is rate-optimal if the iteration period equals the iteration bound. Systematic unfolding of iterative dataflow programs is proposed, and properties of unfolded dataflow programs are studied. Unfolding increases the number of tasks in a program, unravels the hidden concurrently in iterative dataflow programs, and can reduce the iteration period. A special class of iterative dataflow programs, referred to as perfect-rate programs, is introduced. Each loop in these programs has a single register. Perfect-rate programs can always be scheduled rate optimally (requiring no retiming or unfolding transformation). It is also shown that unfolding any program by an optimum unfolding factor transforms any arbitrary program to an equivalent perfect-rate program, which can then be scheduled rate optimally. This optimum unfolding factor for any arbitrary program is the least common multiple of the number of registers (or delays) in all loops and is independent of the node execution times. An upper bound on the number of processors for rate-optimal scheduling is given.>

Techniques for hiding defects caused by lost blocks of lapped orthogonal transform (LOT) coefficients are proposed and compared. By properly enhancing reconstructed blocks, a video system can transmit pleasing images in spite of frequent asynchronous transfer mode (ATM) network losses. The mathematics of LOT calculation suggest several reconstruction strategies. Standard signal-processing techniques such as mean-square-error minimization, time-domain filtering, and LOT-domain coefficient averaging are also investigated and simulated. Comments on the performance of these recovery methods for moving video sequences as well as for single frames are offered.>

A unified framework and terminology is presented for synchronization design in digital systems, borrowing techniques and terminologies from digital system and digital communication design disciplines. The throughput of synchronous and asynchronous interconnect is compared, emphasizing how it is affected by interconnect delay. A discussion is presented of opportunities to apply principles long used in digital communications to the design of digital systems, with the goal of reducing the dependence on interconnect delay.>

The authors describe a clock-free design approach that facilitates modular design without compromising global performance. The goal is to support rapid prototyping of real-time digital signal processing systems with a minimum amount of design effort. The approach allows the scaling up of small prototype systems to very large multiboard systems without concern for global timing problems. The authors address the interconnect schemes applicable to real-time systems and the circuit design techniques for a clock-free implementation.>

The Huffman code is an efficient noiseless coding method for images, video, and other applications. For applications in graphic computers, high-definition televisions (HDTV), and optical fiber networks, Huffman-coded images need to be reconstructed at a high throughput rate. Due to the recursion within the reconstruction algorithm, the achievable throughput rate in a given IC technology is limited by the iteration bound. Methods of relaxing the iteration bound of the reconstruction process, thus increasing the concurrency in the decoding process, are proposed. These methods are simple, effective, and flexible. Unlimited concurrency can be achieved at the expense of additional latency. The incurred overhead is very low, and the complexity increases only linearly with the achieved throughput improvement.>

Since the reconstruction of continuous speech from voice packets is complicated by the variable delays of the packets through the network, a dynamic priority protocol is proposed to minimize the variability of packet delays. The protocol allows the priority of a packet to vary with time. After a discussion of the concept of dynamic priorities, two examples of dynamic priorities are studied through queueing analysis and simulations. Optimal properties of the oldest customer first (OCF) and earliest deadline first (EDF) disciplines are proven, suggesting that they may be theoretically effective in reducing the variability of packet delays. Simulation results of the OCF discipline indicate that the OCF discipline is most effective under conditions of long routes and heavy traffic, i.e., the conditions when delay variability is most likely to be significant. Under OCF, the delays of packets along long routes are improved at the expense of packets along short routes. It is noted that more complex and realistic simulations, including simulations of the EDF discipline, are needed.>

The authors construct a processor design approach that does not require the distribution of a clocking signal. To facilitate design of processors that use fully asynchronous components, the first step is to design hazard-free asynchronous interconnection circuits. To this end, a deterministic algorithm was developed to synthesize asynchronous interconnection circuits from high-level specifications. This approach systematically designs correct asynchronous interconnection circuits with the weakest possible constraints and minimal overhead. The authors are primarily concerned with the synthesis of nonmetastable circuits, even though the procedure is also valid of metastable circuit synthesis. The synthesized logic is hazard-free and guaranteed to have the fastest operation according to a behavioral specification. A high-level description is used to specify circuit behavior, not only for a simpler input format, but also as a basis for determining the final optimum designs. Automatic synthesis and the ability to localize the timing considerations reduce design effort when systems become complex.>

A medium-access protocol called time-slot switching (TSS) is proposed for use in optical-fiber local area networks. This protocol incorporates features of time division, space division, and time compression for users to share a common medium. Very-large-integration (VLSI) CMOS electric crosspoints are used to switch traffic within individual time slots. With these features, data, voice, and video services can all be combined in a single network. In addition, the speed of the electronics can be maximized to match the available optical bandwidth. Operational principles of the TSS protocol are explained. A performance analysis is presented to show the tradeoffs among traffic capacity, frame guard time, blocking probability, and the results show that TSS is more attractive than broadcast protocols for voice traffic or constant-rate data traffic. An approach to integrating voice, data, and video traffic within TSS is also described.>

Seismic migration in the frequency domain using the phase-shift method is a computationally efficient solution of the wave equation. The authors introduce a parallel phase-shift algorithm. This parallel version is implemented on the NCUBE multiprocessing system to solve the wave equation in the frequency domain. Performance issues, some task partitioning strategies, and computation/communication tradeoffs are discussed.>

The authors study seismic migration algorithms in order to develop a general framework for analyzing such algorithms and to propose some coarse-grained paradigms for computation of parallel computers. They analyze a few typical examples of the various migration techniques existing in literature, and discuss methods to optimize their performance on distributed concurrently executing processors. The computational and communication requirements of the algorithms are discussed and diverse optimization techniques are proposed. The memory limitation, I/O bottleneck, and computational tradeoffs on hypercube multiprocessors are analyzed.>

Asynchronous processors, which do not require an external clocking signal, give better performance than comparable synchronous processors in situations for which global synchronization with a high-speed clock becomes a limiting factor to system throughput. Automatic synthesis and the ability to decouple the timing considerations from the design of computational blocks make this approach particularly attractive in reducing design effort when systems become complex. A number of issues relevant to asynchronous programmable processors such as interconnection circuit specifications, circuit design, data flow control, program flow control, feedback and initialization, and I/O interface are discussed.>

The authors explore various approaches to pipelining recursive digital filters. A past attempt to pipeline directly from recursive filters was based on clustered look-ahead computation, which leads to a linear increase in hardware with respect to the number of loop pipeline stages. However, the pipelined filters derived using this technique are not guaranteed to be stable. The authors introduce a new look-ahead approach (referred to as scattered look-ahead) to pipeline recursive filters in a way that guarantees stability. They also propose a decomposition technique to implement the nonrecursive portion (generated due to the scattered look-ahead) in a decomposed manner (for cases where the number of loop pipeline states is a power of two) to obtain pipelined realizations of logarithmic implementation complexity with respect to the number of loop pipeline stages (as opposed to linear). Based on the scattered look-ahead technique, they present fully pipelined and fully hardware efficient bidirectional linear systolic arrays and unidirectional ring arrays for implementation of high speed recursive digital filters.>

Time slot switching (TSS) has been proposed to switch voice, data, and video in a local area network using fiber optics and high-speed CMOS crosspoint switches. For larger networks such as metropolitan area networks (MANs), significant propagation delays necessitate some modifications to the original technique. The authors propose two medium access protocols for MANs; one is called skew time slot switching (STSS), primarily for real-time service such as voice or video, and the other slotted-ring, primarily for data packets. To provide combined voice, video, and data motivates an integration of STSS and slotted-ring. The advantages and performance of these protocols are discussed.>

A technique is described which allows least squares computation to be made at arbitrarily high sampling rates, overcoming the inherent speed limitation due to the recursive algorithms. Previous efforts at high sampling rate systolic implementations of least squares problems have used Givens transformations and QR decomposition, achieving a sampling rate limited by the time required by several multiplication operations. Taking advantage of the linearity of the least squares recursion, the algorithms can be recast into a new realization for which the bound on throughput of least squares computation is arbitrarily high. The technique, which has previously been applied to adaptive lattice filters, is shown to be applicable to the matrix triangularization related problems such as solving general linear systems and computing eigenvalues by the QR algorithm.

The maximum achievable sampling rate of recursive algorithms is inherently bounded due to the computational latency associated with the loop computation. This recursion or feedback in the algorithms destroys the opportunity to pipeline any recursive loop. In this paper, we introduce a technique of look-ahead computation applicable to any linear recursive algorithm (LRA) to achieve equivalent realizations with reduced iteration period and higher sampling rate. The concurrency created by the use of look-ahead computation can be used to obtain pipelined and/or block implementations. We illustrate the applicability of the look-ahead computation technique to obtain high speed VLSI realizations of linear time-invariant, and time-varying systems. A generalized look-ahead computation technique theorem for arbitrary interleaving is also presented. Finally, it is shown that the iteration period in certain synchronous data flow graphs can also be reduced by the use of look-ahead computation.

Data flow is a natural paradigm for describing DSP applications for concurrent implementation on parallel hardware. Data flow programs for signal processing are directed graphs where each node represents a function and each arc represents a signal path. Synchronous data flow (SDF) is a special case of data flow (either atomic or large grain) in which the number of data samples produced or consumed by each node on each invocation is specified a priori. Nodes can be scheduled statically (at compile time) onto single or parallel programmable processors so the run-time overhead usually associated with data flow evaporates. Multiple sample rates within the same system are easily and naturally handled. Conditions for correctness of SDF graph are explained and scheduling algorithms are described for homogeneous parallel processors sharing memory. A preliminary SDF software system for automatically generating assembly language code for DSP microcomputers is described. Two new efficiency techniques are introduced, static buffering and an extension to SDF to efficiently implement conditionals.

Large grain data flow (LGDF) programming is natural and convenient for describing digital signal processing (DSP) systems, but its runtime overhead is costly in real time or cost-sensitive applications. In some situations, designers are not willing to squander computing resources for the sake of programmer convenience. This is particularly true when the target machine is a programmable DSP chip. However, the runtime overhead inherent in most LGDF implementations is not required for most signal processing systems because such systems are mostly synchronous (in the DSP sense). Synchronous data flow (SDF) differs from traditional data flow in that the amount of data produced and consumed by a data flow node is specified a priori for each input and output. This is equivalent to specifying the relative sample rates in signal processing system. This means that the scheduling of SDF nodes need not be done at runtime, but can be done at compile time (statically), so the runtime overhead evaporates. The sample rates can all be different, which is not true of most current data-driven digital signal processing programming methodologies. Synchronous data flow is closely related to computation graphs, a special case of Petri nets. This self-contained paper develops the theory necessary to statically schedule SDF programs on single or multiple processors. A class of static (compile time) scheduling algorithms is proven valid, and specific algorithms are given for scheduling SDF systems onto single or multiple processors.

Special-purpose networks of processors and intelligent switching devices can be programmed to solve problems with inherent parallelism. The target algorithm is coded into a number of asynchronously executing parallel tasks, and assigned to specific processors. For well-known algorithms, information about the data communicated between these tasks (traffic) can be characterized and used by a heuristic algorithm to produce a specialized interconnection network of switching devices at a lower cost and increased performance over the use of a general purpose structure. A program was developed which uses intertask communications to automatically generate interconnection structures of switch chips (SC's). Simulation results were used to compare cost/performance measures for the program-generated networks with some well-known structures, using both statistically generated traffic patterns and the simulation of real applications.

In some adaptive filter applications, particularly echo cancellation, most of the tap coefficients in the convolution sum are essentially zero. We introduce and examine some No-Overkill Schemes (NOS) that eliminate the multiplications required for these zero coefficients by estimating which coefficients are nearly zero and setting them to exactly zero. In addition to reducing computation, this approach has the advantage of reducing the excess mean-square error, since the taps set to zero have no asymptotic fluctuation, Specifically, the NOS schemes work by dynamically partitioning the filter taps into active-taps and zero-taps. We estimate the time to convergence and the reduction in the excess mean-square-error due to the statistical fluctuation of the falter coefficients. Our results indicate that these No-Overkill Schemes significantly reduce the computational requirements with little or no increase in the time to convergence. Robustness of these schemes to a time varying channel is also considered. The NOS schemes increase the control overhead in the implementation of the adaptive filter, so additional examination of implementation tradeoffs for minimum cost is required.

This paper describes systolic realizations of adaptive lattice filters with arbitrarily high sampling rates using relatively slow processing elements. The lattice filter is a desirable structure for this purpose because it can adapt coefficients within each stage using the residual errors from the previous stage and the adaptation algorithms at each stage can be modelled as time-varying linear systems. The properties of independence among stages and linear state-updates make adaptive lattice filters suitable for implementations with arbitrary levels of concurrency. The architecture introduced can be called the vectorized adaptive lattice filter with parallel input and output. It has the property that an arbitrarily high sampling rate can be achieved at the expense of latency. An example of vectorized adaptive lattice filters, the implementation of a normalized prewindowed least-squares lattice predictor, is illustrated, and its latency and complexity are discussed.

The design challenges faced in the integrated circuit realization of the basic customer access U-interface transceiver at 144 kbits/s in the integrated services digital network (ISDN) are summarized. Given the cost and performance objectives, this represents a very challenging design problem from an algorithmic and technology point of view. This survey paper describes the alternative design approaches concentrating on algorithmic issues as opposed to circuit design issues, in the context of the echo cancellation (EC) method of full duplex data transmission. Particular emphasis is given to the areas of echo cancellation, equalization, line code selection, and timing recovery.

Sampled-data techniques are the most practical means of obtaining the necessary signal processing functions for timing recovery in the VLSI implementation of a digital subscriber loop transceiver. The sampled-data timing recovery techniques described in this paper are applicable to both echo cancellation and time-compression multiplexing systems. Timing recovery using baud-rate sampling in conjunction with a special pulse-shaping and timing function fulfills all the objectives for timing recovery in this application. It recovers a timing phase that has minimum precursor intersymbol interference, and makes possible the combination of decision feedback equalizer and echo canceler, reducing the convergence time and increasing the step size. The pulse-shaping function can be performed either in the transmitter by means of digital coding, or in the receiver by means of analog filtering. In the latter case, the transmitted pulse is compatible with more conventional approaches. The proposed partial-response line coding, a special form of AMI coding, is less susceptible to line impairments if detected as a two-level signal. Performance by analysis, simulation, and experimental measurements is reported on a variety of cable configurations, some including bridged taps. Analysis of jitter performance leads to design techniques for reducing the jitter magnitude.

A method of programming an assembler and simulator for a programmable digital signal processor (PDSP) is proposed. This method is general and simple to execute, and makes use of theUNIX®; utilities awk, sed, and grep to translate a source program, consisting of assembly instructions and C statements, to either machine code for the assembler or a C program for the simulator. The approach also provides the advantages that little programming effort is required to generate a new assembler and simulator for another processor instruction set. It also allows a PDSP to be simulated in the context of a larger system containing other PDSP's, other hardware, and an external environment. A disadvantage is that the approach is applicable only to the UNIX operating system.

An approach to the implementation of asynchronous and timing jitter insensitive data echo cancellation is described. This approach introduces a small amount of jitter in the transmitted data signal, or alternatively in the received signal sampling, and uses a simple digital phase-locked loop together with the storage of two sets of echo canceler coefficients. The effect of derived timing jitter on the echo cancellation accuracy is completely eliminated for a loop timed transceiver (as in a digital subscriber loop network termination transceiver), and is easily reduced to negligible levels for a nonloop timed transceiver (as in a digital subscriber loop line card transceiver or a voiceband data modem). In the case of a voiceband data modem, this approach is one method to achieve asynchronous echo cancellation without the need to recover and resample a continuous-time far-end data signal.

Embedded speech coders are characterized by the property that their output quality degrades gracefully as their bit rate is decreased. Design methods for vector quantizers with the embedded coding property are presented and their performance simulated for the medium-band of 32-8 Kbits/sec. Listening tests indicate that these coders can provide good quality speech at 32 and 24 Kbits/sec and intelligible speech down to 8 Kbits/sec.

Studying the effects of roundoff errors in digital filters requires specialized study of each implementation of each of various filter structures. Even the study of these special structures, however, is fraught with difficulties; different implementations of the same structure can have different roundoff behavior, because rounding is done at different points in the structure. The limitations of practical VLSI architectures suggest two models of computation that accurately reflect the vast majority of filter implementations. Such implementations can be accurately described in a factored state variable form that represents the actual computations in the implementations. The quantization noise behavior of different filter structures can be studied under this unified framework. Necessary and sufficient conditions for the optimality of filter realizations expressed in the factored state variable form are derived, as a simple extension of important earlier work with the usual state variable form.

Tradeoffs in the design of the timing recovery functions in a subscriber loop receiver are analyzed. The techniques considered are applicable to both the echo cancellation (EC) and time compression multiplexing (TCM) methods of full duplex transmission. Emphasis is on those techniques that lend themselves to implementation in MOSLSI technology, where the objective requirement is that timing recovery be implemented on a sampled-data signal (with the minimum possible sampling rate where EC is used). The wave difference method (WDM) for timing recovery appears to be the best candidate. A detailed study of its performance is carried out analytically and by computer simulation for the case of binary and alternate mark-inversion (AMI) line coding. A closed form expression describing the binary jitter performance of the WDM and its continuous time counterpart, the spectral line technique, is used to compare the two techniques. Analytical and simulation results for recovered phase and jitter are presented for various cable pulse responses carefully chosen to represent worst-case or nearly worst-case conditions. Two methods for including frequency detection in the WDM, the quadricorrelator and the rotational detector, are also simulated.

A proposed class of vector quantizers with memory, called Predictive Vector Quantizers (PVQ), exhibits good performance (as measured by mean-squared error distortion) for the encoding of speech signals at 16 kbits/sec. Two methods for designing PVQ's are described, and their performance is compared to that of memoryless VQ's by computer simulation. These results indicate that, for comparable performance, the PVQ has a smaller block size and computational load than the memoryless VQ. In addition, preliminary simulations indicate that PVQ's are less speaker dependent than memoryless vector quantizers.

BLOSIM is a general purpose time-driven (as opposed to event-driven) simulation language. It is written in C language, and is intended to provide a highly structured environment for simulations, thereby making practical the accumulation of libraries of simulation routines which can be reused and making multiprogrammer simulation efforts more practical. It is written with the philosophy of not including any simulation primitives within the language itself, but rather complete generality is maintained by having the user provide these as C routines (either coded from scratch or from a user-provided library). It includes as features a hierarchical specification of blocks, interconnection of blocks by first-in first-out buffers, the passing of parameters to blocks, multiple instances of blocks, and automatic scheduling of the order of block execution. It has been used for the multiprogrammer simulation of data transmission and speech processing systems, in both academic and industrial environments, with good results.

LINEMOD is a transmission line modeling program that takes a line configuration (including possibly bridged taps) and generates the input impedance, attenuation versus frequency, and impulse response. It is written in C, a modern structured programming language, and utilizes sophisticated data structures, dynamic storage allocation, and recursion to achieve flexibility and economy of storage. As such, it illustrates the value of C as an implementation language for modeling programs of this type. It also emphasizes a shortcoming of C for this purpose, which is the absence of built-in complex arithmetic.

This tutorial paper reviews echo cancellation techniques as applied to both voice and data transmission applications. The echo control problem in telephone voice transmission is described, and the several measures taken to counteract echo are outlined. The problem of full-duplex data transmission over two-wire lines is described, with application to both digital subscriber loop and voiceband data transmission. The unique characteristics of each of these applications, more advanced methods recently proposed, and approaches to implementation are described.

A new spectral distance measure is defined by inserting a multiplicative frequency weighting term into the conventional Itakura-Saito measure. Then the weighting function is a simple one pole function, then the minimization of the distance between a signal spectrum and an arbitrary N-pole filter results in a set of linear equations that is symmetric and solvable by Cholesky decomposition. When the weighting function is a multiple pole function, the resulting spectral distance minimization produces a set of nonlinear algebraic equations, but fortunately a simple method exists for obtaining an approximate solution which can be refined using the Newton- Raphson method. Results of some preliminary trials in applying the technique to LPC vocoding are described.

This paper reports on studies concerning the feasibility of large-scale integrated realization of the circuits needed to provide hybrid-mode full-duplex digital transmission at 80 kbits/s or higher rates over standard local telephone loops. Alternative means of achieving the required 60 dB or so of echo cancellation have been studied in detail. The conclusion is that a combination of analog and digital circuit techniques permit practical MOSLSI realization of the complete modem, including filters, echo canceller, timing recovery, and A/D and D/A converters, without need for external circuit elements, trimming, or adjustments. The preferred system configuration has been evaluated by means of analysis, simulation, and laboratory and field measurements. A complete full duplex system, including an experimental NMOS integrated circuit echo canceller, was built and tested. Measurements showed a bit error rate lower thanl0^{-8}with line attenuation up to 40 dB, operating at 80 kbits/s. We conclude that a fully integrated MOSLSI ciruit to implement all functions for a hybrid-mode digital local loop is entirely feasible.

This paper describes a new technique for implementing an echo canceller for full-duplex data transmission (such as in digital subscriber loops and volceband data sets). The canceller can operate in spite of time-invariant nonlinearities in the echo channel or in the implementation of the echo canceller itself (such as in the D/A converters). The basic structure of the linear echo canceller is not changed, but taps are simply added to account for the nonlinearity. The number of taps which must be added depends on the degree of nonlinearity which must be compensated. Numerical results based on computer simulation are given which show that typical nonlinearities encountered in MOS D/A converters can be compensated by a relatively small number of taps added to the linear echo canceller, and substantial improvement in the cancellation results.

An approach to the implementation of a discrete cosine transform (DCT) for application to coding speech is described. The approach is oriented toward single speech channel encoding. In addition, a detailed computer simulation of an adaptive transform coder is described. The purpose of the computer simulation is to determine the internal precision at various points in the implementation required to avoid subjective degradation. Specific recommmendations are made on the required internal precision in the implementation of the discrete cosine transform. A breadboard implementation of the DCT using SSI and MSI TTL logic based on the results of the computer simulation is reported.

A comparison of adaptive differential pulse code modulation (ADPCM) speech compression systems is made using different recursive adaptive linear prediction algorithms. The particular algorithms considered are 1) a fixed predictor, 2) the adaptive least mean square (LMS) transversal predictor, 3) the LMS (gradient) lattice predictor, 4) the leas squares (LS) lattice predictor, and 5) an LS lattice predictor combined with a third-order pitch inverse filter. The results indicate that for the conditions simulated, the difference in system performance using the different adaptive algorithms is negligible, suggesting that the predictor having the simplest implementation is the best.

The sensitivity of a lattice filter pole location to perturbation of the PARCOR coefficients determines the number of bits of precision required for scalar quantization of those coefficients in LPC. It is demonstrated that the sensitivity characteristics can be altered without sacrificing the desirable properties of the lattice filter. Further, it is argued that for speech it is desirable to lower the sensitivity at low frequencies at the expense of higher frequencies, which can be accomplished by a simple one- pole allpass transformation. The resulting reduction in bit rate is comparable to that obtained by preemphasis.

A simple model characterizing the convergence properties of an adaptive digital lattice filter using gradient algorithms has been reported [1]. This model is extended to the least mean square (LMS) lattice joint process estimator, to the recursive least squares (LS) algorithms, and is compared with computer simulations. Interestingly, the LS models are more accurate than the previous LMS models. In addition, although the LS lattice consistently converges somewhat faster than the LMS lattice, they both exhibit similar behavior.

Recursive equations for the first-order zero movement sensitivities of the all-zero digital lattice filter are given. In addition to being useful for numerical evaluation, these equations allow general conclusions to be drawn concerning the quite different sensitivity properties of early and final stages. The approach differs from previous sensitivity studies, which considered measures consisting of integrals of the ratio of the deviated spectrum to the original spectrum, and is therefore more useful in directly studying the sensitivity of formant bandwidth and center frequencies when the filter is used in speech synthesis.

Convergence properties of a continuously adaptive digital lattice filter used as a linear predictor are investigated for both an unnormalized and a normalized gradient adaptation algorithm. The PARCOR coefficient mean value and the output mean square error are approximated and a simple model is described which approximates these quantities as functions of time. Calculated curves using this model are compared with simulation results. Results obtained for a two stage lattice are then compared with the two-stage 1ms transversal filter algorithm, demonstrating that it is possible but unlikely for the transversal filter to converge faster than the analogous lattice filter.

Two implementations of an adaptive balancing hybrid are described. The first is predominly analog, in which the adaptation parameter θ is a continuous analog quantity, while the second is predominly digital, in which θ has a two-bit representation. Experimental results are reported.

A new form of adaptive balancing hybrid is proposed for application to the two-wire to four-wire interface of a local digital switch. It is similar to an echo canceller but with a single degree of freedom and much simpler circuitry. In this paper a theory of operation of the hybrid is developed, and in a companion paper two circuit implementations and experimental results are reported.

The mean-square errors (MSE) of individual subsystems of a signal processing system generally don't add up to equal the overall MSE, due to mutual correlations among the errors on the individual subsystems. This makes it difficult to interpret the magnitude of contribution of each subsystem to the MSE. It is shown that if the MSE of each subsystem is defined alternatively as the MSE between conditional mean estimators of the original signal at the input and output of that subsystem, then the overall MSE is in fact the sum of the MSE's of individual subsystems. Several examples illustrate the usefulness of this principle in understanding the source of system impairments.

The effect of bit robbing in tandem digital switches is shown to consist of a time-varying linear distortion comparable to aliasing distortion in addition to increased quantization distortion. Alternative bit-robbing strategies in which this linear distortion can be reduced or eliminated are evaluated, and recommendations are made for future digital switch designs.

A significant problem in phase-locked loop (PLL) timing and carrier extraction is the initial acquisition. Very narrow loop bandwidths are generally required to control phase jitter, and acquisition may depend on an extremely accurate initial VCO frequency (VCXO) or sweeping. We describe two simply implemented frequency detectors which, when added to the traditional phase detector, can effect acquisition even with very small loop bandwidths and large initial frequency offsets. The first is the quadricorrelator, previously applied to timing recovery by Bellisio, while the second is new, and called a rotational frequency detector. The latter, while limited to lower frequencies and higher signal-to-noise ratios, is suitable for many applications and can be implemented with simpler circuitry.

This paper presents a telecommunications system, KEYPAC (Key Phone Alphanumeric Communication), that enables a user to communicate over the telephone without the use of speech. The design of this system was motivated by the need for a low cost, yet simple and useful means of telephone communication in the deaf community. The KEYPAC system provides a flexible means for speechless telephone communication by utilizing an ordinary pushbutton telephone as a transmitting device. Alphanumeric messages are sent by pressing sequences of keys according to a simple coding scheme of two keys per letter and one key per number (0-9). Message reception is accomplished with the use of a small, hand-held receiver that is attached to the telephone. The receiver decodes sequences of D.T.M.F. (Dual Tone Multi Frequency) audio tones and displays the resulting messages on a visual display or hard copy printer.

The mean-square errors (mse) of individual links of a communication network generally do not add up to the overall mse because of mutual correlations among the errors on the individual links. This makes it difficult to interpret the magnitude of contribution of each link to the mse. It is shown that if the mse of each link is defined alternatively as the mse between conditional mean estimators of the original signal at the input and output of that link, then the overall mse is in fact the sum of the mse's on individual links. Several examples illustrate the usefulness of this principle, particularly in digital communications, in understanding the source of system impairments.

Several aspects of the design of digital frequency synthesizers are considered, and a detailed analysis of the spectral purity of digitally synthesized frequencies is given. These results are then applied to a specific application: the testing of A/D and D/A converters.

The optimum minimum MSE equalization, both linear and decision feedback, of a digital fiber optic transmission system with Poisson signal statistics and additive wide-sense stationary noise is considered. The problem is reduced to the solution of a certain integral equation, with solutions obtained for certain special cases, including white and band-limited additive noise. Numerical results are given for white noise and an exponential input pulse.

In a PLL frequency synthesizer, the reference and VCO frequencies are divided down to their greatest common divisor frequency prior to phase comparison. We replace the dividers by a simplified form of digital frequency synthesizer, and examine the spectrum of the phase comparator outputs to show that the loop bandwidth can be dramatically increased, thereby improving the pull-in range and acquisition time.

The technique of nearly instantaneous companding (NIC) that we describe processesn-bit μ-law or A-law encoded pulse-code modulation (PCM) to a reduced bit rate. A block ofNsamples (typicallyN \cong 10) is searched for the sample having the largest magnitude, and each sample in the block is then reencoded to a nearly uniform quantization having (n - 2) bits and an overload point at the top of the chord of the maximum sample. Since an encoding of this chord must be sent to the receiver along with the uniform reencoding, the resulting bit rate isf_{s}(n -2 + 3/N)bits/s where fsis the sampling rate. The algorithm can be viewed as an adaptive PCM algorithm that is compatible with the widely used μ-law andA-law companded PCM. Theoretical and empirical evidence is presented which indicates a performance slightly better than (n - 1) bit companded PCM (the bit rate is close to that of (n - 2) bit PCM). A feature which distinguishes NIC from most other bit-rate reduction techniques is a performance that is largely insensitive to the statistics of the input signal.

Harashima and Miyakawa [1] and Tomlinson [2] have described a generalized partial response technique which achieves the performance of the decision-feedback equalizer without the error propagation problem. We show here that when the equalized and baud-rate sampled channel assumes the special rationalztransformF(Z) =\frac{\sum\min{i=0}\max{M}{g_{i}Z^{i}}{1/L\sum\min{i=0}\max{N}{l_{i}Z^{i}wherel_{0} = L, g_{0} = 1, thegiandliare integers, andLis a power of 2, the implementation can assume an especially simple form not requiring the storage of analog samples. The numerator polynomial can be chosen to achieve transmission zeros, as in ordinary partial response, while the denominator can be chosen to reduce the noise enhancement in equalization. This technique results in as much as a doubling of the peak transmitted voltage and, as in ordinary partial response, an increase in the number of received levels. It is shown that on thef^{1/2}channel characteristic of coaxial cable, most of the noise advantage of decision-feedback equalization can be achieved with a moderate number of received levels, and that some of this noise advantage can be traded for a reduced number of received levels. The greatest advantage accrues in multilevel transmission because of the lower peak transmitted voltage penalty.

An upper bound on the error probability of a decision-feedback equalizer which takes into account the effect of error propagation is derived. The bound, which assumes independent data symbols and noise samples, is readily evaluated numerically for arbitrary tap gains and is valid for multilevel and nonequally likely data. One specific result for equally likely binary symbols is that if the worst case intersymbol interference when the firstJfeedback taps are Set to zero is less than the original signal voltage, then the error probability is multiplied by at most a factor of2^Jrelative to the error probability in the absence of decision errors at highS/Nratios. Numerical results are given for the special case of exponentially decreasing tap gains. These results demonstrate that the decision-feedback equalizer has a lower error probability than the linear zero-forcing equalizer when there is both a highS/Nratio and a fast roll-off of the feedback tap gains.

The entropy at the output of a quantizer is equal to the average mutual information between unquantized and quantized random variables. Thus, for a fixed number of quantization levels, output entropy is a reasonable information-theoretic criterion of quantizer fidelity. It is shown that, for a class of signal distributions, which includes the Gaussian, the quantizers with maximum output entropy (MOE) and minimum average error (MAE) are approximately the same within a multiplicative constant.