The paper examines tradeoffs between speed and quality of codebook/generation algorithms and offers new ways to produce excellent codebooks with only modest computation cost. It compares the performance of four algorithms for constructing codebooks. The LBG method of Linde, Buzo, and Gray (1980) produces the best codebooks but requires the most computation. The method by Equitz (1987, 1989) produces codebooks nearly as good and requires somewhat less computation. It describes a new method based on eigenvector subdivision that produces useable codebooks in a fraction of the computational effort of either of the other methods. A fourth hybrid method yields very good codebooks with modest computation by using the eigenvector subdivision method to obtain a first approximation that is refined with LBG optimization.>

A method is presented for automatically translating a concurrent program into an asynchronous circuit. The translation procedure involves a simple syntax-directed translation from program constructs into initial asynchronous circuits. The resulting circuits are improved with correctness-preserving circuit-to-circuit transformations similar to peephole optimization in conventional compilers. Because these steps can be proved to be correct, the programmer is guaranteed that any specification met by the program will also be met by the circuit. A system has been constructed to perform the translation automatically. A brief description of the method is given, followed by two examples of programs translated into circuits.>

Asynchronous designs are of increasing interest because of the cost of broadcasting clocks over large areas of a chip. A tool for comparing implementations of speed-independent circuits with specifications is described. Petri nets are used throughout as a user-level description language. These are translated into trace structures, which can then be processed by an existing automatic verifier. This tool is applied to a nontrivial self-timed queue design.>

With widespread use of raster scan displays and the ever-increasing desire for faster interactivity, higher image complexity, and higher resolution in displayed images, several techniques have been proposed for rasterizing primitive graphical objects. This paper characterizes the performance of these techniques and shows how they evolve for more complex images on higher resolution displays. This characterization will not only show the strengths and deficiencies of existing rasterization techniques, but will also reveal new architectures for future raster graphics systems.

This paper describes a display system designed to make the recording and rearrangement of bits in a frame-buffer display system convenient and rapid.The advantage of frame-buffer displays is that because the intensity of each pixel can be specified independently, any picture can be displayed.The disadvantage is that a great many bits in the frame-buffer memory must be changed to make major changes in the picture.The 8 by 8 display described in this paper gets its name from the fact that in a single memory cycle it can access any 8 by 8 square of pixels.Internal shifters and special memory addressing circuits are provided to make the access independent of word boundaries in the memory.Pixel manipulation functions are included to process the 64 pixels thus accessed, mask them, overwrite them with new information, or combine them logically with other pixels.The resulting data can be stored into any other 8 by 8 square of pixels in a subsequent memory cycle.Looping mechanisms implemented in microcode provide RasterOp functions that transfer information from any rectangular area of the display to any other area with or without intervening pixelmodification operations.The prototype system is able to copy the entire 768 by 1024 array of the display in 52 ms, or two frame times.The ability to rearrange data quickly has proved to be an asset for character generation, line drawing, and picture construction, as well as for scrolling and other rearrangements of material already displayed on the screen.A simple model is developed to compare the performance of the 8 by 8 memory system with conventional frame-buffer organization.Execution traces of Smalltalk display programs are applied to the model to obtain figures of merit for different hardware organizations.

DeriveA wide variety of line-drawing algorithms can be derived by applying program transformations to a simple, obviously correct algorithm.The transformations increase the speed of the algorithm and eliminate the need for floating-point computations.We show how Bresenham's algorithm can be derived in this way.The transformations are then used to derive several variants of Bresenham's algorithm, designed for use on displays that can generate more than one pixel at a time.The treatment shows a complete, extended example of the practical use of program transformations.

While simple line-drawing techniques produce “jagged” lines on raster images, more complex anti-aliasing, or filtering, techniques use gray-scale to give the appearance of smooth lines and edges. Unfortunately, these techniques are not frequently used because filtering is thought to require considerable computation. This paper presents a simple algorithm that can be used to draw filtered lines; the inner loop is a variant of the Bresenham point-plotting algorithm. The algorithm uses table lookup to reduce the computation required for filtering. Simple variations of the algorithm can be used to draw lines with different thicknesses and to smooth edges of polygons.

Interactive use of a display requires the capability to update the display rapidly. This paper describes an on-going project at Carnegie-Mellon University in which we are designing a frame buffer raster-scan display system which has the high performance typically required for interactive display applications. The system is intended to be a display for personal computers, computer generated graphic images, and image processing applications. Built using smart VLSI memory chips, the system will use parallel processing techniques to provide high performance.

System design is undergoing radical changes that are significant both for the graphics community and for other design communities in which the principal hardware resources are those obtained via catalogues of parts. The drive to reduce system costs forces us to design at the lowest level possible, i.e., on silicon; only in this way can we reduce the number of packaged components, thereby reducing the number of interconnecting wires, board space and power requirements. This, in turn, presents a system design dilemma. The large cost of designing silicon systems, i.e. VLSI, conflicts with the need to design them to reduce cost. As a result, novel new design aids are being devised that actually make integrated system design easier than conventional system design; integrated systems can be thoroughly simulated because simple models of them exist at every level of representation.

Accompanying the rapid development of integrated circuit fabrication technology has been a parallel, but slower, development of IC design techniques and systems. Recent approaches to IC design enable individual designers to consider developing their own VLSI circuits. Such capability may open the door to a more varied set of system designs than could previously be considered in most design environments.

Raster-scan display terminals can significantly improve the quality of interaction with conventional computer systems. The design of a graphics package to provide a “window” into the extensive programming environment of interlisp is presented. Two aspects of the package are described: first, the functional view of display output and interactive input facilities as seen by the programmer, and second, the methods used to link the display terminal to the main computer via a packet-switched computer network. Recommendations are presented for designing operating systems and programming languages so as to simplify attaching display terminals.

The file system and modularization of a single-user operating system are described. The main points of interest are the openness of the system, which establishes no sharp boundary between itself and the user's programs, and the techniques used to make the system robust.