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 (2^q – 1) natural numbers ranging from 1 to (2^q-1).

USE OF IBS: (1) Interlaced Analog to Digital Converter (IADC), and (2) Compression of Binary Data Irrespective of Source Files.

Evaluation Report by Lambert & Lambert

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 log₂n 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 2^q 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 =L_IBS (say)] trials to search out simultaneously all 2^(q-1) leaves of a complete binary search tree of depth q formed from first (2^q – 1) natural numbers ranging from 1 to (2^q-1). Whereas total run time to search 2^q-1 leaves of complete binary search tree T of 2^q nodes with binary search (BS) = q.2^q-1 = L_BS (say);

L_BS – L_IBS = q.2^q-1 -5.2^q-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 log₂n. 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

Page updated

Google Sites

Report abuse