Springer Series in Information Sciences

Charles K. Chui · Guanrong Chen · Teuvo Kohonen · Manfred R. Schroeder

Latest release: November 11, 2013

Series

Books

Book 1·Dec 2012

Due to continual progress in the large-scale integration of semiconductor circuits, parallel computing principles can already be met in low-cost sys tems: numerous examples exist in image processing, for which special hard ware is implementable with quite modest resources even by nonprofessional designers. Principles of content addressing, if thoroughly understood, can thereby be applied effectively using standard components. On the other hand, mass storage based on associative principles still exists only in the long term plans of computer technologists. This situation is somewhat confused by the fact that certain expectations are held for the development of new storage media such as optical memories and "spin glasses" (metal alloys with low-density magnetic impurities). Their technologies, however, may not ripen until after "fifth generation" computers have been built. It seems that software methods for content addressing, especially those based on hash coding principles, are still holding their position firmly, and a few innovations have been developed recently. As they need no special hardware, one might expect that they will spread to a wide circle of users. This monograph is based on an extensive literature survey, most of which was published in the First Edition. I have added Chap. ?, which contains a review of more recent work. This updated book now has references to over 1200 original publications. In the editing of the new material, I received valuable help from Anneli HeimbUrger, M. Sc. , and Mrs. Leila Koivisto.

Content-Addressable Memories

Book 1·Dec 2012

0.0

Designers and users of computer systems have long been aware of the fact that inclusion of some kind of content-addressable or "associative" functions in the storage and retrieval mechanisms would allow a more effective and straightforward organization of data than with the usual addressed memories, with the result that the computing power would be significantly increased. However, although the basic principles of content-addressing have been known for over twenty years, the hardware content-addressable memories (CAMs) have found their way only to special roles such as small buffer memories and con trol units. This situation now seems to be changing: Because of the develop ment of new technologies such as very-large-scale integration of semiconduc tor circuits, charge-coupled devices, magnetic-bubble memories, and certain devices based on quantum-mechanical effects, an increasing amount of active searching functions can be transferred to memory units. The prices of the more complex memory components which earlier were too high to allow the application of these principles to mass memories will be reduced to a fraction of the to tal system costs, and this will certainly have a significant impact on the new computer architectures. In order to advance the new memory principles and technologies, more in formation ought to be made accessible to a common user.

Fast Fourier Transform and Convolution Algorithms: Edition 2

Book 2·Dec 2012

4.0

In the first edition of this book, we covered in Chapter 6 and 7 the applications to multidimensional convolutions and DFT's of the transforms which we have introduced, back in 1977, and called polynomial transforms. Since the publication of the first edition of this book, several important new developments concerning the polynomial transforms have taken place, and we have included, in this edition, a discussion of the relationship between DFT and convolution polynomial transform algorithms. This material is covered in Appendix A, along with a presentation of new convolution polynomial transform algorithms and with the application of polynomial transforms to the computation of multidimensional cosine transforms. We have found that the short convolution and polynomial product algorithms of Chap. 3 have been used extensively. This prompted us to include, in this edition, several new one-dimensional and two-dimensional polynomial product algorithms which are listed in Appendix B. Since our book is being used as part of several graduate-level courses taught at various universities, we have added, to this edition, a set of problems which cover Chaps. 2 to 8. Some of these problems serve also to illustrate some research work on DFT and convolution algorithms. I am indebted to Mrs A. Schlageter who prepared the manuscript of this second edition. Lausanne HENRI J. NUSSBAUMER April 1982 Preface to the First Edition This book presents in a unified way the various fast algorithms that are used for the implementation of digital filters and the evaluation of discrete Fourier transforms.

Fast Fourier Transform and Convolution Algorithms

Book 2·Mar 2013

4.0

This book presents in a unified way the various fast algorithms that are used for the implementation of digital filters and the evaluation of discrete Fourier transforms. The book consists of eight chapters. The first two chapters are devoted to background information and to introductory material on number theory and polynomial algebra. This section is limited to the basic concepts as they apply to other parts of the book. Thus, we have restricted our discussion of number theory to congruences, primitive roots, quadratic residues, and to the properties of Mersenne and Fermat numbers. The section on polynomial algebra deals primarily with the divisibility and congruence properties of polynomials and with algebraic computational complexity. The rest of the book is focused directly on fast digital filtering and discrete Fourier transform algorithms. We have attempted to present these techniques in a unified way by using polynomial algebra as extensively as possible. This objective has led us to reformulate many of the algorithms which are discussed in the book. It has been our experience that such a presentation serves to clarify the relationship between the algorithms and often provides clues to improved computation techniques. Chapter 3 reviews the fast digital filtering algorithms, with emphasis on algebraic methods and on the evaluation of one-dimensional circular convolutions. Chapters 4 and 5 present the fast Fourier transform and the Winograd Fourier transform algorithm.

Pitch Determination of Speech Signals: Algorithms and Devices

Book 3·Dec 2012

0.0

Pitch (i.e., fundamental frequency FO and fundamental period TO) occupies a key position in the acoustic speech signal. The prosodic information of an utterance is predominantly determined by this parameter. The ear is more sensitive to changes of fundamental frequency than to changes of other speech signal parameters by an order of magnitude. The quality of vocoded speech is essentially influenced by the quality and faultlessness of the pitch measure ment. Hence the importance of this parameter necessitates using good and reliable measurement methods. At first glance the task looks simple: one just has to detect the funda mental frequency or period of a quasi-periodic signal. For a number of reasons, however, the task of pitch determination has to be counted among the most difficult problems in speech analysis. 1) In principle, speech is a nonstationary process; the momentary position of the vocal tract may change abruptly at any time. This leads to drastic variations in the temporal structure of the signal, even between subsequent pitch periods, and assuming a quasi-periodic signal is often far from realistic. 2) Due to the flexibility of the human vocal tract and the wide variety of voices, there exist a multitude of possible temporal structures. Narrow-band formants at low harmonics (especially at the second or third harmonic) are an additional source of difficulty. 3) For an arbitrary speech signal uttered by an unknown speaker, the fundamental frequency can vary over a range of almost four octaves (50 to 800 Hz).

Pattern Analysis and Understanding: Edition 2

Book 4·Apr 2013

0.0

In this second edition every chapter of the first edition of Pattern Analysis has been updated and expanded. The general view of a system for pattern analysis and understanding has remained unchanged, but many details have been revised. A short account of light and sound has been added to the introduction, some normalization techniques and a basic introduction to morphological operations have been added to the second chapter. Chapter 3 has been expanded significantly by topics like motion, depth, and shape from shading; additional material has also been added to the already existing sections of this chapter. The old sections of Chap. 4 have been reorganized, a general view of the classification problem has been added and material provided to incorporate techniques of word and object recognition and to give a short account of some types of neural nets. Almost no changes have been made in Chap. 5. The part on representation of control structures in Chap. 6 has been shortened, a section on the judgement of results has been added. Chapter 7 has been rewritten almost completely; the section on formal grammars has been reduced, the sections on production systems, semantic networks, and knowledge acquisition have been expanded, and sections on logic and explanation added. The old Chaps. 8 and 9 have been omitted. In summary, the new edition is a thorough revision and extensive update of the first one taking into account the progress in the field during recent years.

Pattern Analysis

Book 4·Dec 2012

0.0

This book is devoted to pattern analysis, that is, the automatic construc tion of a symbolic description for a complex pattern, like an image or con nected speech. Pattern analysis thus tries to simulate certain capabilities which go without saying in any human central nervous system. The increasing interest and growing efforts at solving the problems related with pattern analysis are motivated by the challenge of the problem and the expected ap plications. Potential applications are numerous and result from the fact that data can be gathered and stored by modern devices in ever increasing extent, thus making the finding of particular interesting facts or events in these hosts of data an ever increasing problem. It was tried to organize the book around one particular view of pattern analysis: the view that pattern analysis requires an appropriate set of modules operating on a common data base which contains interme processing diate results of processing. Although other views are certainly possible, this one was adopted because the author feels that it is a useful idea, be cause the size of this book had to be kept within reasonable bounds, and because it facilitated the composition of fairly self-contained chapters.

Image Sequence Analysis

Book 5·Nov 2013

0.0

The processing of image sequences has a broad spectrum of important applica tions including target tracking, robot navigation, bandwidth compression of TV conferencing video signals, studying the motion of biological cells using microcinematography, cloud tracking, and highway traffic monitoring. Image sequence processing involves a large amount of data. However, because of the progress in computer, LSI, and VLSI technologies, we have now reached a stage when many useful processing tasks can be done in a reasonable amount of time. As a result, research and development activities in image sequence analysis have recently been growing at a rapid pace. An IEEE Computer Society Workshop on Computer Analysis of Time-Varying Imagery was held in Philadelphia, April 5-6, 1979. A related special issue of the IEEE Transactions on Pattern Anal ysis and Machine Intelligence was published in November 1980. The IEEE Com puter magazine has also published a special issue on the subject in 1981. The purpose of this book is to survey the field of image sequence analysis and to discuss in depth a number of important selected topics. The seven chap ters fall into two categories. Chapters 2, 3, and 7 are comprehensive surveys on, respectively, the whole field of image sequence analysis, efficient coding of image sequences, and the processing of medical image sequences. In Chapters 1, 4, 5, and 6 the authors present mainly results of their own research on, respectively, motion estimation, noise reduction in image sequences, moving object extraction, and occlusion.

Picture Engineering

Book 6·Dec 2012

0.0

Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity, Edition 4

Book 7·Jan 2006

3.0

"Number Theory in Science and Communication" is a well-known introduction for non-mathematicians to this fascinating and useful branch of applied mathematics . It stresses intuitive understanding rather than abstract theory and highlights important concepts such as continued fractions, the golden ratio, quadratic residues and Chinese remainders, trapdoor functions, pseudoprimes and primitive elements. Their applications to problems in the real world are one of the main themes of the book. This revised fourth edition is augmented by recent advances in primes in progressions, twin primes, prime triplets, prime quadruplets and quintruplets, factoring with elliptic curves, quantum factoring, Golomb rulers and "baroque" integers.

From reviews of earlier editions –

"I continue to find [Schroeder’s] Number Theory a goldmine of valuable information. It is a marvellous book, in touch with the most recent applications of number theory and written with great clarity and humor.’ Philip Morrison (Scientific American)

"A light-hearted and readable volume with a wide range of applications to which the author has been a productive contributor – useful mathematics outside the formalities of theorem and proof." Martin Gardner

Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity, Edition 5

Book 7·Nov 2008

0.0

"Number Theory in Science and Communication" is a well-known introduction for non-mathematicians to this fascinating and useful branch of applied mathematics . It stresses intuitive understanding rather than abstract theory and highlights important concepts such as continued fractions, the golden ratio, quadratic residues and Chinese remainders, trapdoor functions, pseudo primes and primitive elements. Their applications to problems in the real world are one of the main themes of the book. This revised fifth edition is augmented by recent advances in coding theory, permutations and derangements and a chapter in quantum cryptography.

From reviews of earlier editions –

"I continue to find [Schroeder’s] Number Theory a goldmine of valuable information. It is a marvelous book, in touch with the most recent applications of number theory and written with great clarity and humor.’ Philip Morrison (Scientific American)