NDLI: Some intractable problems in digital signal processing

Content Provider	IEEE Xplore Digital Library
Author	Cappello, P. Steiglitz, K.
Copyright Year	1981
Description	Author affiliation: Princeton University, Princeton, N.J. (Cappello, P.)
Abstract	Over the past decade a large class of problems, called NP-complete[1], have been shown to be equivalent in the sense that if a fast algorithm can be found for one, fast algorithms can be found for all. At the same time, despite much effort, no fast algorithms have been found for any, and these problems are widely regarded as intractable. This class includes such notoriously difficult problems as the traveling salesman problem, graph coloring, and satisfiability of Boolean expressions. This paper describes some problems in digital signal processing which are NP-complete. These include: (1) Minimize the number of registers required to implement a signal flow graph; (2) Minimize the time to perform the additions (multiplications) of a signal flow graph using P adders (multipliers); (3) Minimize the computational cost for multiplication by a fixed matrix. Large-scale instances of such problems may become important with the use of VLSI technology to implement signal processing.
Starting Page	43
Ending Page	46
File Size	110218
Page Count	4
File Format	PDF
DOI	10.1109/ICASSP.1981.1171300
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1981-03-30
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Digital signal processing Signal processing algorithms Flow graphs Traveling salesman problems Registers Adders Computational efficiency Large-scale systems Very large scale integration Signal processing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Some complexity issues in digital signal processing

Implementation aspects of lattice bilinear digital ladder filters

On quantization effects in state-variable filter implementations

VLSI implementation of residue-to-binary converters for digital signal processing

High speed merged multiplication

An efficient algorithm for traveling salesman problems based on self-organizing feature maps

VLSI bit-sequential architectures for digital signal processing

Digital processing structures for VLSI implementation

Implementing algorithms for convolution on arrays of adders

Some intractable problems in digital signal processing

Similar Documents

Some complexity issues in digital signal processing

Implementation aspects of lattice bilinear digital ladder filters

On quantization effects in state-variable filter implementations

VLSI implementation of residue-to-binary converters for digital signal processing

High speed merged multiplication

An efficient algorithm for traveling salesman problems based on self-organizing feature maps

VLSI bit-sequential architectures for digital signal processing

Digital processing structures for VLSI implementation

Implementing algorithms for convolution on arrays of adders

Some intractable problems in digital signal processing