Persistent Link:
http://hdl.handle.net/10150/609697
Title:
COMPLEXITY OF PCM FORMATTING
Author:
Jones, Charles H.; Gardner, Lee S.
Affiliation:
Edwards Air Force Base
Issue Date:
1997-10
Rights:
Copyright © International Foundation for Telemetering
Collection Information:
Proceedings from the International Telemetering Conference are made available by the International Foundation for Telemetering and the University of Arizona Libraries. Visit http://www.telemetry.org/index.php/contact-us if you have questions about items in this collection.
Publisher:
International Foundation for Telemetering
Journal:
International Telemetering Conference Proceedings
Abstract:
How difficult is it to develop a pulse code modulation (PCM) stream data format? Specifically, given a size, in bits, and a set of parameter sample rates, how hard is it to find a mapping of the sample rates that fits into the frame size -- if one even exists? Using telemetry trees this paper will show that the number of possible mappings for a given set of parameters and sample rates grows exponentially in terms of the number of parameters. The problem can thus be stated in terms of finding a specific instance, or showing that no such instance exists, among an exponentially large number of potential mappings. Although not proof, this provides strong evidence that the PCM format design problem is NP-complete (meaning it is a member of nondeterministic polynomial space but not a member of deterministic polynomial space). That is, that the problem can not be solved in polynomial time and would take a computer years or centuries to solve relatively small instances of the problem. However, if the problem requirements are relaxed slightly, telemetry trees can be used to reduce the PCM formatting problem to linear time in terms of the number of parameters. This paper describes a technique that can provide an optimal and fully packed PCM format.
Sponsors:
International Foundation for Telemetering
ISSN:
0884-5123; 0074-9079
Additional Links:
http://www.telemetry.org/

Full metadata record

DC FieldValue Language
dc.language.isoen_USen
dc.titleCOMPLEXITY OF PCM FORMATTINGen_US
dc.contributor.authorJones, Charles H.en
dc.contributor.authorGardner, Lee S.en
dc.contributor.departmentEdwards Air Force Baseen
dc.date.issued1997-10-
dc.rightsCopyright © International Foundation for Telemeteringen
dc.description.collectioninformationProceedings from the International Telemetering Conference are made available by the International Foundation for Telemetering and the University of Arizona Libraries. Visit http://www.telemetry.org/index.php/contact-us if you have questions about items in this collection.en
dc.publisherInternational Foundation for Telemeteringen
dc.description.abstractHow difficult is it to develop a pulse code modulation (PCM) stream data format? Specifically, given a size, in bits, and a set of parameter sample rates, how hard is it to find a mapping of the sample rates that fits into the frame size -- if one even exists? Using telemetry trees this paper will show that the number of possible mappings for a given set of parameters and sample rates grows exponentially in terms of the number of parameters. The problem can thus be stated in terms of finding a specific instance, or showing that no such instance exists, among an exponentially large number of potential mappings. Although not proof, this provides strong evidence that the PCM format design problem is NP-complete (meaning it is a member of nondeterministic polynomial space but not a member of deterministic polynomial space). That is, that the problem can not be solved in polynomial time and would take a computer years or centuries to solve relatively small instances of the problem. However, if the problem requirements are relaxed slightly, telemetry trees can be used to reduce the PCM formatting problem to linear time in terms of the number of parameters. This paper describes a technique that can provide an optimal and fully packed PCM format.en
dc.description.sponsorshipInternational Foundation for Telemeteringen
dc.identifier.issn0884-5123-
dc.identifier.issn0074-9079-
dc.identifier.urihttp://hdl.handle.net/10150/609697-
dc.identifier.journalInternational Telemetering Conference Proceedingsen
dc.typetexten
dc.typeProceedingsen
dc.relation.urlhttp://www.telemetry.org/en
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.