interlacedadconverter
Interlaced Analog to Digital Converter (IADC)
Parallel I/O Analog to Digital Converter
Invention Title: Interlaced Analog to Digital Conversion (IADC)
Invention Theme: Parallel I/O A/D Converter Using 1 D/A Converter
Invention Aim: Improvement of Successive Approximation A/D Converter (SADC) Using
Time Division Multiplexing (TDM)
Invention Algorithm: Interlaced Binary Search Algorithm (IBS)
Invention Advantage: Simultaneous Multiple Items Search in Binary Search Tree
Algorithm Improves: IBS improves Binary Search Algorithm
IBS searches simultaneously multiple items in the binary search tree with better run time efficiency than that of binary search algorithm that searches multiple items sequentially. IBS searches multiple items in a interwave or interlace fashion.
THEOREM I: Interlaced Binary Search will consume [5.2(q-2)-2.q+2] trials to search out simultaneously all 2(q-1) leaves of a complete binary search tree of depth q formed from first (2q – 1) natural numbers ranging from 1 to (2q-1).
USE OF IBS: (1) Interlaced Analog to Digital Converter (IADC), and (2) Compression of Binary Data Irrespective of Source Files.
IADC Critices Over SADC: If input analog values are either 'closely spaced' or 'reside in leaves of the binary search tree' or combination of these two the search effiency will increase a lot. So appropriate scaling of input values will bring high efficiency in IADC implementation. This will resemble to parallel conversions of all inputs through parallel SADCs - 1 SADC per input.
Problem this invention is intended to solve
The invention is removing drawbacks of successive approximation analog to digital (A/D) converter (SADC) that uses one digital to analog (D/A) converter, time division multiplexing (TDM) and binary search algorithm to convert multiple analog inputs to digital equivalent. Drawbacks are (1) due to log2n limit of the run time of binary search, input signal variation rate and leakage in S&H (sample and hold) circuits total number of inputs is limited to a low value and (2) S&H circuits require high synchronised clock signal.
Invention description
IADC uses 1 DAC similar to successive approximation ADC but reads simultaneously all inputs instead of TDM. IADC uses Interlaced Binary Search (IBS) algorithm that is the base invention. IBS removes drawbacks of BS that are inability to search multiple items simultaneously and search efficiency limited by log(n) base 2. IADC will fit in applications that requires simultaneous multiple analog to digital conversions.
Summery Of The Invention:
The invention, Interlaced Analog to Digital Converter (IADC) having a microarchitecture that is microprogrammed with the Interlaced Binary Search (IBS) algorithm that can search n items in one scan through the sorted list of 2q items where search path of any item out of n items is depended in an ‘interlaced fashion’ with search paths of remaining items. The ‘interlaced fashion’ is the inter woven characteristic of the IBS by which search path of any item is related to the search paths of other remaining items for which search for matches yet to be continued, as IBS searches all n items in a single run through T. For n=2(q-1) and each item is a leaf of T, IADC using IBS will consume [5.2(q-2)-2.q+2 =LIBS (say)] trials to search out simultaneously all 2(q-1) leaves of a complete binary search tree of depth q formed from first (2q – 1) natural numbers ranging from 1 to (2q-1). Whereas total run time to search 2q-1 leaves of complete binary search tree T of 2q nodes with binary search (BS) = q.2q-1 = LBS (say);
LBS – LIBS = q.2q-1 -5.2q-2 + 2.q – 2 = (2(q-2) + 1) (2.q – 5) + 3.
The invention IADC uses one digital to analog converter to generate trial points. For one approximation run IADC reads (samples and holds, S&H) all n inputs simultaneously without time division multiplexing. IADC uses improved binary search procedure that is termed as Interlaced Binary Search (IBS). IBS runs through same complete binary search tree that is used by binary search in a successive approximation analog to digital converter. IBS has overcome the limitations of binary search that are search of multiple items in a single run and for multiple items’ search crossing the complexity limit of binary search that is log2n. In IADC number of trials and selection of trial points depend on the number of inputs and dissimilarities among input values that is search path of any input is ‘interlaced’ or in other word, ‘interwoven’ with search paths of other remaining inputs for which search for matches yet to be continued.
Invention presentation
IADC is a modification of successive approximation ADC. IADC requires 1 DAC, n sample and hold (S/H) circuits without TDM but simultaneous S/H, n q-bit output binary registers (q is resolution of IADC), 4n binary flags, 4 q-bit binary registers ( 1 for DAC input and 3 for intermediate data hold register) and IBS logic circuit.
Invention illustration
IADC Illustrations: These illustrations derived from ‘C’ simulation of IADC, are explaining the working principle of IADC and especially uniqueness of IBS algorithm. Out() signifies output binary register.
Working Principle:
7 items to be searched from a sorted list of 256 items i.e. resolution is of 8 bits
Input_0 =A0=1, Input_1=A1=5, Input_2=A2=9, A3=12, A4=14, A5=19, A6=28.
Trial Points Are: 128, 64, 32, 16, 8, 4, 2,[out(0)=] 1, 3, 7,[out(1)=] 5, 15, 11,[out(2)=] 9, 10, 11, 15, 13,[out(3)=] 12, 15,[out(4)=] 14, 31, 23,[out(5)=] 19, 21, 22, 23, 31, 27, 29,[out(6)=] 28,
Total Trial = 31
Here we are presenting four sample runs of IADC for searching arbitrary 8 items from a sorted list of 256 items. Inputs are not mentioned explicitly, instead output match is given, e.g. [out(7)=] 26 describes match for input-7 (A7) is completed and value of input-7 is 26.
1:Trial Points Are: 128, 64, 32, 16, 24, 28, [out(7)=] 26, 27, 31, 63, 47, 55, 51, 49,[out(6)=] 48, 127, 95, 111, 103, 107,[out(1)=] 105, 106, 107, 111, 127, 119, 123,[out(0)=] 121, 255, 191, 159, 175, 167, 163,[out(3)=] 165, 166, 167, 175, 191, 183,[out(2)=] 179, 181, 182, 183, 191, 255, 223, 207, 215, 211, 213,[out(4)=] 214, 215, 223, 255, 239, 247, 243, 245,[out(5)=] 246,
Total Trial = 60
0 is taken as a special case of 1.
2:Trial Points Are:[out(3)=] 128,[out(1)=] 64,[out(0)=] 32, 48, 56, 60, 62, 63, 127, 95, 111, 103, 99, 97,[out(2)=] 96,[out(7)=] 255, 191, 159, 175, 167, 163, 161 ,[out(4)=] 160, 163, 167, 175, 191, 255, 223, 207, 199, 195, 193,[out(5)=] 192, 195, 199, 207, 223, 255, 239, 231, 227, 225,[out(6)=] 224,
Total Trial = 44
0 is taken as a special case of 1.
3:Trial Points Are: 128, 64, 32, 16, 24, 28,[out(0)=] 30, 31, 63, 47, 55, 59, 61,[
out(1)=] 62, 127, 95, 79, 87, 91, 93,[out(2)=] 94, 95, 127, 111, 119, 123, 125,[
out(3)=] 126, 255, 191, 159, 143, 151, 155, 157,[out(4)=] 158, 159, 191, 175, 18
3, 187, 189,[out(5)=] 190, 191, 255, 223, 207, 215, 219, 221,[out(6)=] 222, 223,
255, 239, 247, 251, 253,[out(7)=] 254,
Total Trial = 58
4: Trial Points Are: 128, 64, 32, 16, 24, 28, 30,[out(0)=] 31,[out(1)=] 63,[out(3)=] 127,[out(2)=] 95,[out(7)=] 255,[out(5)=] 191,[out(4)=] 159, 175, 183, 187, 189, 190, 191, 255,[out(6)=] 223,
Total Trial = 22
0 is taken as a special case of 1. Searching 0 does not count to Total Trial points
Illustration of Worst Case of IBS: Only 2 inputs and will not occur as IADC is multiple inputs much greater than 2.
Trial Points Are: 128, 64, 32, 16, 8, 4, 2,[out(0)=] 1, 3, 7, 15, 31, 63, 127, 255, 191, 223, 207, 199, 195, 193,[out(1)=] 192,
Total Trial = 22
Illustration of Best Case of IBS: Number of trial points is equal to Number of items to be searched.
Trial Points Are:[out(0)=] 128,[out(1)=] 64,[out(2)=] 32,[out(3)=] 16,[out(4)=]
8,[out(5)=] 4,[out(6)=] 2,[out(7)=] 1, [out(8)=] 3,[out(9)=] 7,[out(10)=] 15,[out(11)=] 31,[out(12)=] 63,[out(13)=] 127,[out(14)=] 255,
Total Trial = 15
0 is taken as a special case of 1. Searching 0 does not count to Total Trial point
Separate Runs of IBS for Searching All Nodes of a Particular Level of a Complete Binary Search Tree of Depth ‘8’.
1: LEVEL-1 NODES.
Trial Points Are: 128,[out(0)=] 64, 96, 112, 120, 124, 126, 127, 255, 191, 223, 207, 199, 195, 193,[out(1)=] 192. Total Trial = 16
2: LEVEL-2 NODES.
Trial Points Are: 128, 64,[out(0)=] 32, 48, 56, 60, 62, 63, 127, 95, 111, 103, 99, 97,[out(1)=] 96, 255, 191, 159, 175, 167, 163, 161,[out(2)=] 160, 163, 167, 175, 191, 255, 223, 239, 231, 227, 225,[out(3)=] 224,
Total Trial = 34
0 is taken as a special case of 1. Searching 0 does not count to Total Trial points
3: LEVEL-3 NODES.
Trial Points Are: 128, 64, 32,[out(0)=] 16, 24, 28, 30, 31, 63, 47, 55, 51, 49,[out(1)=] 48, 127, 95, 79, 87, 83, 81,[out(2)=] 80, 83, 87, 95, 127, 111, 119, 115, 113,[out(3)=] 112, 255, 191, 159, 143, 151, 147, 145,[out(4)=] 144, 147, 151, 159, 191, 175, 183, 179, 177,[out(5)=] 176, 179, 183, 191, 255, 223, 207, 215,211, 209,[out(6)=] 208, 211, 215, 223, 255, 239, 247, 243, 241,[out(7)=] 240,
Total Trial = 66
0 is taken as a special case of 1. Searching 0 does not count to Total Trial points
4: LEVEL-4 NODES.
Trial Points Are: 128, 64, 32, 16,[out(0)=] 8, 12, 14, 15, 31, 23, 27, 25,[out(1)=] 24, 63, 47, 39, 43, 41,[out(2)=] 40, 43, 47, 63, 55, 59, 57,[out(3)=] 56, 127, 95, 79, 71, 75, 73,[out(4)=] 72, 75, 79, 95, 87, 91, 89,[out(5)=] 88, 91, 95, 127, 111, 103, 107, 105,[out(6)=] 104, 107, 111, 127, 119, 123, 121,[out(7)=] 120, 255, 191, 159, 143, 135, 139, 137,[out(8)=] 136, 139, 143, 159, 151, 155, 153,[out(9)=] 152, 155, 159, 191, 175, 167, 171, 169,[out(10)=] 168, 171, 175, 191, 183, 187, 185,[out(11)=] 184, 187, 191, 255, 223, 207, 199, 203, 201,[out(12)=] 200, 203, 207, 223, 215, 219, 217,[out(13)=] 216, 219, 223, 255, 239, 231, 235, 233,[out(14)=] 232, 235, 239, 255, 247, 251, 249,[out(15)=] 248,
Total Trial = 116
0 is taken as a special case of 1. Searching 0 does not count to Total Trial points
5: LEVEL-5 NODES.
Trial Points Are: 128, 64, 32, 16, 8,[out(0)=] 4, 6, 7, 15, 11, 13,[out(1)=] 12, 31, 23, 19, 21,[out(2)=] 20, 23, 31, 27, 29,[out(3)=] 28, 63, 47, 39, 35, 37,[out(4)=] 36, 39, 47, 43, 45,[out(5)=] 44, 47, 63, 55, 51, 53,[out(6)=] 52, 55, 63, 59, 61,[out(7)=] 60, 127, 95, 79, 71, 67, 69,[out(8)=] 68, 71, 79, 75, 77,[out(9)=] 76, 79, 95, 87, 83, 85,[out(10)=] 84, 87, 95, 91, 93,[out(11)=] 92, 95, 127, 111, 103, 99, 101,[out(12)=] 100, 103, 111, 107, 109,[out(13)=] 108, 111, 127, 119, 115, 117,[out(14)=] 116, 119, 127, 123, 125,[out(15)=] 124, 255, 191, 159, 143, 135, 131, 133,[out(16)=] 132, 135, 143, 139, 141,[out(17)=] 140, 143, 159, 151, 147, 149,[out(18)=] 148, 151, 159, 155, 157,[out(19)=] 156, 159, 191, 175, 167, 163, 165,[out(20)=] 164, 167, 175, 171, 173,[out(21)=] 172, 175, 191, 183, 179, 181,[out(22)=] 180, 183, 191, 187, 189,[out(23)=] 188, 191, 255, 223, 207, 199, 195, 197,[out(24)=] 196, 199, 207, 203, 205,[out(25)=] 204, 207, 223, 215, 211, 213,[out(26)=] 212, 215, 223, 219, 221,[out(27)=] 220, 223, 255, 239, 231, 227, 229,[out(28)=] 228, 231, 239, 235, 237,[out(29)=] 236, 239, 255, 247, 243, 245,[out(30)=] 244, 247, 255, 251, 253,[out(31)=] 252,
Total Trial = 184
0 is taken as a special case of 1. Searching 0 does not count to Total Trial points
6: LEVEL-6 NODES.
Trial Points Are: 128, 64, 32, 16, 8, 4,[out(0)=] 2, 3, 7, 5,[out(1)=] 6, 15, 11, 9,[out(2)=] 10, 11, 15, 13,[out(3)=] 14, 31, 23, 19, 17,[out(4)=] 18, 19, 23,21,[out(5)=] 22, 23, 31, 27, 25,[out(6)=] 26, 27, 31, 29,[out(7)=] 30, 63, 47, 39, 35, 33,[out(8)=] 34, 35, 39, 37,[out(9)=] 38, 39, 47, 43, 41,[out(10)=] 42, 43, 47, 45,[out(11)=] 46, 47, 63, 55, 51, 49,[out(12)=] 50, 51, 55, 53,[out(13)=] 54, 55, 63, 59, 57,[out(14)=] 58, 59, 63, 61,[out(15)=] 62, 127, 95, 79, 71, 67, 65,[out(16)=] 66, 67, 71, 69,[out(17)=] 70, 71, 79, 75, 73,[out(18)=] 74, 75,79, 77,[out(19)=] 78, 79, 95, 87, 83, 81,[out(20)=] 82, 83, 87, 85,[out(21)=] 86, 87, 95, 91, 89,[out(22)=] 90, 91, 95, 93,[out(23)=] 94, 95, 127, 111, 103, 99, 97,[out(24)=] 98, 99, 103, 101,[out(25)=] 102, 103, 111, 107, 105,[out(26)=] 106, 107, 111, 109,[out(27)=] 110, 111, 127, 119, 115, 113,[out(28)=] 114, 115, 119, 117,[out(29)=] 118, 119, 127, 123, 121,[out(30)=] 122, 123, 127, 125,[out(31)=] 126, 255, 191, 159, 143, 135, 131, 129,[out(32)=] 130, 131, 135, 133,[out(33)=] 134, 135, 143, 139, 137,[out(34)=] 138, 139, 143, 141,[out(35)=] 142, 143, 159, 151, 147, 145,[out(36)=] 146, 147, 151, 149,[out(37)=] 150, 151, 159, 155, 153,[out(38)=] 154, 155, 159, 157,[out(39)=] 158, 159, 191, 175, 167, 163, 161,[out(40)=] 162, 163, 167, 165,[out(41)=] 166, 167, 175, 171, 169,[out(42)=] 170, 171, 175, 173,[out(43)=] 174, 175, 191, 183, 179, 177,[out(44)=] 178, 179, 183, 181,[out(45)=] 182, 183, 191, 187, 185,[out(46)=] 186, 187, 191, 189,[out(47)=] 190, 191, 255, 223, 207, 199, 195, 193,[out(48)=] 194, 195, 199, 197,[out(49)=] 198, 199, 207, 203, 201,[out(50)=] 202, 203, 207, 205,[out(51)=] 206, 207, 223, 215, 211, 209,[out(52)=] 210, 211, 215, 213,[out(53)=] 214, 215, 223, 219, 217,[out(54)=] 218, 219, 223, 221,[out(55)=] 222, 223, 255, 239, 231, 227, 225,[out(56)=] 226, 227, 231, 229,[out(57)=] 230, 231, 239, 235, 233,[out(58)=] 234, 235, 239, 237,[out(59)=] 238, 239, 255, 247, 243, 241,[out(60)=] 242, 243, 247, 245,[out(61)=] 246, 247, 255, 251, 249,[out(62)=] 250, 251, 255, 253,[out(63)=] 254,
Total Trial = 311
0 is taken as a special case of 1. Searching 0 does not count to Total Trial points
7: LEVEL-7 NODES. Simultaneous Search for all leaves of Binary Search tree of Depth 8 (Theorem-1 Illustration):
Trial Points Are: 128, 64, 32, 16, 8, 4, 2,[out(0)=] 1,[out(1)=] 3,[out(3)=] 7,[out(2)=] 5,[out(7)=] 15,[out(5)=] 11,[out(4)=] 9, 10, 11, 15,[out(6)=] 13,[out(15)=] 31,[out(11)=] 23,[out(9)=] 19,[out(8)=] 17, 18, 19, 23,[out(10)=] 21, 22, 23, 31,[out(13)=] 27,[out(12)=] 25, 26, 27, 31,[out(14)=] 29,[out(31)=] 63,[out(23)=] 47,[out(19)=] 39,[out(17)=] 35,[out(16)=] 33, 34, 35, 39,[out(18)=] 37, 38, 39, 47,[out(21)=] 43,[out(20)=] 41, 42, 43, 47,[out(22)=] 45, 46, 47, 63,[out(27)=] 55,[out(25)=] 51,[out(24)=] 49, 50, 51, 55,[out(26)=] 53, 54, 55, 63,[out(29)=] 59,[out(28)=] 57, 58, 59, 63,[out(30)=] 61,[out(63)=] 127,[out(47)=] 95,[out(39)=] 79,[out(35)=] 71,[out(33)=] 67,[out(32)=] 65, 66, 67, 71,[out(34)=] 69,70, 71, 79,[out(37)=] 75,[out(36)=] 73, 74, 75, 79,[out(38)=] 77, 78, 79, 95,[out(43)=] 87,[out(41)=] 83,[out(40)=] 81, 82, 83, 87,[out(42)=] 85, 86, 87, 95,[out(45)=] 91,[out(44)=] 89, 90, 91, 95,[out(46)=] 93, 94, 95, 127,[out(55)=] 111,[out(51)=] 103,[out(49)=] 99,[out(48)=] 97, 98, 99, 103,[out(50)=] 101, 102, 103, 111,[out(53)=] 107,[out(52)=] 105, 106, 107, 111,[out(54)=] 109, 110, 111, 127,[out(59)=] 119,[out(57)=] 115,[out(56)=] 113, 114, 115, 119,[out(58)=] 117, 118, 119, 127,[out(61)=] 123,[out(60)=] 121, 122, 123, 127,[out(62)=] 125,[out(127)=] 255,[out(95)=] 191,[out(79)=] 159,[out(71)=] 143,[out(67)=] 135,[out(65)=] 131,[out(64)=] 129, 130, 131, 135,[out(66)=] 133, 134, 135, 143,[out(69)=] 139,[out(68)=] 137, 138, 139, 143,[out(70)=] 141, 142, 143, 159,[out(75)=] 151,[out(73)=] 147,[out(72)=] 145, 146, 147, 151,[out(74)=] 149, 150, 151, 159,[out(77)=] 155,[out(76)=] 153, 154, 155, 159,[out(78)=] 157, 158, 159, 191,[out(87)=] 175,[out(83)=] 167,[out(81)=] 163,[out(80)=] 161, 162, 163, 167,[out(82)=] 165, 166, 167, 175,[out(85)=] 171,[out(84)=] 169, 170, 171, 175,[out(86)=] 173, 174, 175, 191,[out(91)=] 183,[out(89)=] 179,[out(88)=] 177, 178, 179, 183,[out(90)=] 181, 182, 183, 191,[out(93)=] 187,[out(92)=] 185, 186, 187, 191,[out(94)=] 189, 190, 191, 255,[out(111)=] 223,[out(103)=] 207,[out(99)=] 199,[out(97)=] 195,[out(96)=] 193, 194, 195, 199,[out(98)=] 197, 198, 199, 207,[out(101)=] 203,[out(100)=] 201, 202, 203, 207,[out(102)=] 205, 206, 207, 223,[out(107)=] 215,[out(105)=] 211,[out(104)=] 209, 210, 211, 215,[out(106)=] 213, 214, 215, 223,[out(109)=] 219,[out(108)=] 217, 218, 219, 223,[out(110)=] 221, 222, 223, 255,[out(119)=] 239,[out(115)=] 231,[out(113)=] 227,[out(112)=] 225, 226, 227, 231,[out(114)=] 229, 230, 231, 239,[out(117)=] 235,[out(116)=] 233, 234, 235, 239,[out(118)=] 237, 238, 239, 255,[out(123)=] 247,[out(121)=] 243,[out(120)=] 241, 242, 243, 247,[out(122)=] 245, 246, 247, 255,[out(125)=] 251,[out(124)=] 249, 250, 251, 255,[out(126)=] 253,
Total Trial = 306
0 is taken as a special case of 1. Searching 0 does not count to Total Trial points
[5.2(q-2)-2.q+2]q=8 = 5.2(8-2)-2.8+2=306.
Fields of Application
Replacement of ADC using TDM. Special note to process control instrumentation. Also the algorithm IBS is used in another application of data encoding (patent pending).
Advantages of this invention
IADC will reduce total number of ADC that uses successive approximation and TDM to convert a lot of analog signals to digital equivalents.
Development stage
TEXT only
Type of Documentation available
Detail description and C simulation
The Inventor(s) Name(s): (1) aloke SARKAR, (2) basudha SARKAR, (3) sila SARKAR
Self introduction: 2 Engineering Degrees - (1) Electronics & Communication and (2) computer. 2 inventions management thoughts. 7 India national level and 2 International level papers. May refer http://alokeinweb.googlepages.com/
Owner of the invention: yes. basudha SARKAR, sila SARKAR
3. Protection
Patent No. 221740 (45/CAL/2002), Dated 24/01/2002 Granted On Dated 03/07/2008
Priority: 24 JANUARY 2002
Countries where it is in force: INDIA
4. Business intention
Selling and/or Licencing
5. Contact
Name: ALOKE SARKAR
E-mail: aloke412@rediffmail.com , basudhasarkar@rediffmail.com
Tel.: 91-9778400134, 91-9937462614, 91-661-2640289
Address: C-38, SECTOR-9, ROURKELA, ORISSA, INDIA. PIN-769009