Digital Commons Network^™

High Rate Concatenated Coding Systems Using Multidimensional Bandwidth Efficient Inner Codes, Robert H. Deng, Daniel J. Jr. Costello

Research Collection School Of Computing and Information Systems

A concatenated coding system using two-dimensional trellis-coded MPSK inner codes and Reed-Solomon outer codes for application in high-speed satellite communication systems was proposed previously by the authors (ibid., vol.37, no.5, p.420-7, May 1989). The authors extend their results to systems using symbol-oriented, multidimensional, trellis-coded MPSK inner codes. The concatenated coding systems are divided into two classes according to their achievable effective information rates. The first class uses multidimensional trellis-coded 8-PSK inner codes and achieves effective information rates around 1 b/dimension (spectral efficiency 2 b/s/Hz). The second class employs multidimensional trellis-coded 16-PSK inner codes and provides effective information rates around 1.5 …

A Relaxation Algorithm For Segmentation Of The Endocardial Surface From Cine Ct, William A. Barrett, Bryan S. Morse

Faculty Publications

A relaxation algorithm has been developed for automated segmentation of the endocardial surface from contrast Cine CT images. The image is contoured at an initial density threshold and a one-dimensional edge operator is applied orthogonally to each point of the contour. Output from the operator is used to generate a histogram, the mode of which identifies a new threshold. The image is contoured again at the new threshold and the process is repeated. Iteration continues with successive threshold estimates converging to a stable value in the region of the endocardial surface. Computer-determined thresholds compare favorably with manual segmentation while reducing …

Probabilistic Segmentation Of Myocardial Tissue By Deterministic Relaxation, William A. Barrett, Shawn C. Becker, Jerome A. Broekhuijsen

Faculty Publications

A recently-developed probabilistic model for automatically segmenting regions of interest in abdominal CT scans has been adapted to the challenging task of segmenting myocardial tissue in Cine CT scans. A system has been implemented on relatively low-cost hardware which performs such segmentations. Special techniques have been developed to improve consistency and accuracy. Early results of testing this new modality are encouraging and promising. Based on observations from experimentation, new directions for future work have been identified.

Interactive Measurement Of Three-Dimensional Cardiac Morphology, William A. Barrett, Shawn C. Becker

Faculty Publications

Techniques have been developed for extracting three-dimensional (3D) measurements directly and interactively from 3D representations of Cine CT images. In order to obtain 3D measurements the anatomical surface is interrogated directly through the use of a 3D graphical "probe" (line). The probe is interactively positioned and stretched between any visible surface points to allow direct capture of 3D (linear) distance. Distance measurements are updated in real time as the probe dynamically "penetrates" any intervening anatomy while providing valuable depth cuing for visual feedback and probe placement. Curvilinear distance is obtained by stretching the probe over multiple surface points. The probe …

Two-Dimensional Pattern Matching With K Mismatches, Sanjay Ranka, Todd Heywood

Electrical Engineering and Computer Science - Technical Reports

We give an algorithm which finds all occurrences of an m1 x m2 pattern array embedded as subarrays in an n1 x n2 array of text, where at most k mismatches are allowed per occurrence. The algorithm runs in time O((k+a)(blogb+ n1n2)), where a = min(m1m2) and b=max(m1m2). This improves upon the previously best known algorithm, and is asymptotically optimal for k ≈ a.

Embedding Meshes On The Star Graph, Sanjay Ranka, Jhy-Chun Wang, Nangkang Yeh

Electrical Engineering and Computer Science - Technical Reports

We develop algorithms for mapping n-dimensional meshes on a star graph of degree n with expansion 1 and dilation 3. We show that an n degree star graph can efficiently simulate an n-dimensional mesh.

An O(H^6) Quintic Spline Collocation Method For Second Order Two-Point Boundary Value Problems, M. Irodotou-Ellina, Elias N. Houstis, S. B. Kim

Department of Computer Science Technical Reports

No abstract provided.

Expert System For Interpreting An Organizational Climate Survey Supporting Guided Development, Thabet Birro

Theses and Dissertations

This project has lead to the development of a prototype, diagnostic, rule-based expert system to analyze data gathered with an organizational climate survey conducted in high technology firms. The development process followed an investigative look at the field of expert systems. The project was implemented using Level5 shell (by Level 5 research Inc.) in PC/MS-DOS environment.

Analysis Of A Parallel Mergesort, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

The paper describes a performance model of a fine-grained, parallel mergesort which sorts N elements in 0(N) time using 0(logN) processors. The model predicts both the communication time involved in merging the elements and the decomposition time required to activate and terminate the binary tree of processes. The parallel algorithm is written in Joyce and runs on an Encore Multimax.

Term Rewriting With Conditionals And Priority Orderings, Chilukuri K. Mohan

Electrical Engineering and Computer Science - Technical Reports

Conditional rewriting and priority rewriting are two recent generalizations of term rewriting systems. In the former, each rewrite rule is accompanied by an antecedent which must be shown to hold before rewriting can occur. In the latter, rewrite rules can be used only in a particular order. We compare these formalisms: neither formalism encompasses the other in a practical sense, but we give restrictions under which priority and conditional rewriting can be equivalent. We combine the two operational mechanisms, obtaining a natural and expressive formalism called Priority Conditional Rewriting Systems (PCRS). PCRS can be used to “fully-define” data type specifications …

A 15-Valued Algorithm For Test Pattern Generation, Akhtar Uz Zaman, M. Ali, Carlos R.P. Hartmann

Electrical Engineering and Computer Science - Technical Reports

In this report we present a new algorithm for detecting single stuck-at faults in combinational circuits. This algorithm is based on a 15-valued system and introduces several new concepts to make test generation more efficient. This 15-valued system allows us to impose all the constraints that must be satisfied in order to sensitize a single path. Consequently all deterministic implications are fully considered prior to the enumeration process. The resulting ability to identify inconsistencies prior to enumeration improves the possibility of quicker identification of redundant faults. Instead of sensitizing a single gate at a time, we sensitize subpaths by sensitizing …

Center For Computer And Information Sciences Interim Application Package 1989, Nova University

College of Engineering and Computing Course Catalogs

No abstract provided.

Parity Retransmission Hybrid Arq Using Rate 1/2 Convolutional Codes On A Nonstationary Channel, L. R. Lugand, D. J. Costello, Jr., Robert H. Deng

Research Collection School Of Computing and Information Systems

A parity retransmission hybrid automatic repeat request (ARQ) scheme is proposed which uses rate 1/2 convolutional codes and Viterbi decoding. A protocol is described which is capable of achieving higher throughputs than previously proposed parity retransmission schemes. The performance analysis is based on a two-state Markov model of a nonstationary channel. This model constitutes a first approximation to a nonstationary channel. The two-state channel model is used to analyze the throughput and undetected error probability of the protocol presented when the receiver has both an infinite and a finite buffer size. It is shown that the throughput improves as the …

Towards A Bound For The Compression Of The Lzw Algorithm, Anoop Kumar Srivastava, Shinu Gupta

Theses

The LZW algorithm is a well known efficient adaptive compression algorithm. It is based on constructing a dictionary containing character strings from the text. A number of researchers have attempted to add variations to the original algorithm to achieve higher compression values. In this thesis we attempt to find a bound for the LZW approach. That is, we build a dictionary which gives maximum compression and satisfies prefix property of LZW algorithm.

In order to build such an optimum dictionary, the dynamic programming technique is applied. The final dictionary selected consists of entries which give maximum overall compression and also …

Interpolation Search For Alphabetic Tables, Loizos Gabriel

Theses

One of the fastest search techniques for uniformly distributed sorted numerical tables is interpolation search. This divide and conquer technique accesses the most probable key rather than the middle key as in binary search and continues to search similarly the appropriate part of the table . In the previous work we proved a lg lg n average number of accesses for interpolation search.

The inefficiency of interpolation search for an alphabetic table is demonstrated by Burton and Lewis and a robust variation suggested by them to improve the efficiency. This inefficiency is expected since such tables are usually far from …

Cascading Lzw Algorithm With Huffman Coding : A Variable To Variable Length Compression Algorithm, Ashish Khandubhai Mehta

Theses

Two common schemes in data compression are fixed to variable length coding and variable to fixed length coding. Higher compression is expected from the more flexible scheme of variable to variable length coding. In such a scheme a compression dictionary is used to transfer variable length string over the text alphabet into variable length strings over the coding alphabet. The compression is achieved due to matching longer more frequent text strings with shorter coding strings.

To obtain a variable to variable length coding we choose to cascade the LZW , variable to fixed , coding with the Huffman , fixed …

Automated Translation Of Digital Logic Equations Into Optimized Vhdl Code, John Evan Stark, George Winston Zobrist

Computer Science Technical Reports

It was desired to develop an algorithm for the automated translation of finite slate machines from state table form to optimized VHDL form. To do this, algorithms arc needed for reducing the state machine to simplest form, making state assignments, producing minimal logic equations to represent the state machine, and producing VHDL code which describes the intended circuit. Various such algorithms were examined and a prototype program written to perform this translation.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, May 1989, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A ten page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

High Rate Concatenated Coding Systems Using Bandwidth Efficient Trellis Inner Codes, Robert H. Deng, D. J. Costello, Jr.

Research Collection School Of Computing and Information Systems

High-rate concatenated coding systems with bandwidth-efficient trellis inner codes and Reed-Solomon (RS) outer codes are investigated for application in high-speed satellite communication systems. Two concatenated coding schemes are proposed. In one the inner code is decoded with soft-decision Viterbi decoding, and the outer RS code performs error-correction-only decoding (decoding without side information). In the other the inner code is decoded with a modified Viterbi algorithm, which produces reliability information along with the decoded output. In this algorithm, path metrics are used to estimate the entire information sequence, whereas branch metrics are used to provide reliability information on the decoded sequence. …

In The Image Of Man: Reflections On Artificial Intelligence, Noreen L. Herzfeld

Theology Faculty Publications

No abstract provided.

Parameter Non-Stationarity In A Model To Estimate The Business Value Of Information Technology, Robert J. Kauffman

Research Collection School Of Computing and Information Systems

Developing robust and refined measures to quantify strategic impacts is a major challenge facing researchers who seek to improve methods for IT investment evaluation. This paper presents a means to test for parameter "non-stationarity" in a model which quantifies the strategic contribution of IT. An iterative "jackknife" procedure is used to diagnose if different local competitive and demographic conditions present in branch banking enhance or suppress leverage on deposit market share associated with membership in an ATM network. Preliminary results suggest this approach will be useful for managers who need to evaluate similar ITs which operate in different environments.

The Nature Of Parallel Programming, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

Parallel programming is the art of writing programs for computers that perform many operations simultaneously. This essay discusses the nature of parallel programming without going into technical details. It uses a sorting problem to illustrate what it means to solve a problem in parallel, how we write parallel programs, how parallel computers execute them, and how fast they run. The author expects that scientific users of parallel computers may find ease of programming more important than maximum performance. He suggests ways to make this possible.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, March 1989, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A ten page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Impacts Of Industrial Robotics: Potential Effects On Labor And Costs Within The Metalworking Industries, Steven M. Miller

Research Collection School Of Computing and Information Systems

According to leading expert opinion, industrial robots are among the most important innovations of recent decades. Yet there is very considerable uncertainty (and disagreement) as to the rate at which the use of robots will spread and what their effects on employment, costs, and market structure will be. As stressed in 1983 by Congress’s Office of Technology Assessment: “A central question for an analysis of the social and economic impacts of programmable automation is whether programmable automation is likely to spread especially rapidly among firms and industries, and why.” The author analyzes the job displacement effects of industrial robots, as …

Method For Automatic Level Matching In A Local Network, In Particular A Multicomputer Arrangement, Comprising A Bus System Having Lightwaves Guides, For The Purpose Of Collision Recognition, Hans Thinschmidt, Franz J. Kurfess

Computer Science and Software Engineering

A method is disclosed for automatic level matching in a local network, particularly for a multicomputer arrangement, comprising an optical bus system, for the purpose of collision recognition. Given a required level matching, the process is executed such that a fundamental phase is provided in which level matching devices respectively individually assigned to the computers are synchronized with one another. A first matching phase is provided in which all level matching devices simultaneously execute a process for setting a reference voltage to the lowest received level, whereby the sum of all attenuation components of the signal path at the receiving …

An Improved Exact Graph Coloring Algorithm, Thomas J. Sager, Shi-Jen Lin

Computer Science Technical Reports

We present two algorithms for exact graph coloring of the vertex sequential with dynamic reordering of vertices variety. The first, W-DEG, is a straight-forward improvement on Korman’s original algorithm. The second, SWAP2, is a not so straight forward improvement on Korman’s algorithm and appears to offer the best performance of known exact graph coloring algorithms.

A Color-Exchange Algorithm For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin

Computer Science Technical Reports

DEXCH, a color-exchange exact graph coloring algorithm is presented. On many classes of graphs, DEXCH can, in the mean, find the chromatic number of a graph considerably faster than the DSATUR algorithm. The improvement over DSATUR stems from the ability to reorganize the subset of colored vertices and to detect in certain instances the existence of a complete subgraph of cardinality equal to the number of colors used in the best coloring found so far. The mean improvement over DSATUR is greatest on high edge-density graphs attaining the value of 42% on random graphs of edge-density 0.7 on 64 vertices.

A Pruning Procedure For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin

Computer Science Technical Reports

The graph coloring problem can be stated: “Given an undirected graph, using a minimal number of colors, assign each vertex a color so that if two vertices are connected by an edge then they are not assigned the same color.” Graph coloring can be used to solve scheduling problems with constraints of the form: events e and e' can not be scheduled together. Graph coloring is an NP-Complete problem. Generally large problems are solved heuristically, although some of the better heuristic algorithms use an exact graph coloring algorithm to finish coloring a graph after first reducing it heuristically …

A Logic Programming Elucidation Of Oda - Document Descriptions And Processes, Howard A. Blair, Allen Brown Jr.

Electrical Engineering and Computer Science - Technical Reports

We are pursuing a programme of research in document representation. The principal aim of this research is to develop a document description language that has a precise formal semantics, that is fully expressive of the constructs typical of traditional (procedural) document description languages, that is constraint-based, and that cleanly separates specifications of form and content. The research is currently in the first of three envisioned three phases. In the first phase we are formalising the Office Document Architecture (ODA) by faithfully translating ODA document descriptions into logic programmes. The transition utilizes highly restricted forms of Prolog programmes.1 In the second …

Augustine’S Mathematical Realism, Paul Zwier

ACMS Journal 2004

This paper begins by outlining an argument advanced against mathematical realism by Philip Kitcher. It then sketches the life and work of the great Christian philosopher and theologian, Augustine of Hippo. It discusses Augustine’s view that there exist eternal ideas in the mind of God that God used as templates in his creation of material objects. Among these are ideas about numbers and other mathematical objects. It also discusses Augustine’s understanding of how human beings have access to such ideas. It concludes with a discussion of some possible objections to Augustine’s perspective.