Can You Prove the Time Bound for ANDing N Signals with Varying Arrival Times?

[CuppoJava]

Homework Statement

There are N signals that must be all ANDed together using two-input AND gates, and produce a result as fast as possible.

The N signals arrive at different times (T1 to TN)

An AND gate first waits for both input signals to arrive, and then takes 1 second to output the resultant signal.

Prove that, no matter whatever scheme is used, the shortest calculation time satisfies :

Total time >= log2( sum( 2^Ti) )

And that the optimal scheme guarantees:

Total time <= log2( sum(2^Ti) ) + 1

The Attempt at a Solution

Following a derivation similar to the derivation for the Huffman code, I have proven that the optimal scheme is to always combine the two earliest signals, at anyone point in time.

But I can't prove that this scheme satisfies the specified bound.

Thanks for your help
-Patrick

 

[mighty2000]

Dear Patrick,

Thank you for sharing your attempt at a solution. Your approach of using a derivation similar to the Huffman code is a good start. However, I believe there may be a simpler way to prove the given bound.

Let's assume that the N signals arrive in increasing order of time, i.e. T1 < T2 < ... < TN. In order to minimize the total calculation time, we want to minimize the number of AND gates used. This can be achieved by always combining the two earliest arriving signals at any given point in time.

Now, let's consider the total number of AND gates used in this scheme. Since we are always combining the two earliest signals, the number of AND gates used at any point in time is equal to the number of signals that have already arrived. This means, at time T1, we use 1 AND gate, at time T2, we use 2 AND gates, and so on, until at time TN, we use N AND gates. Therefore, the total number of AND gates used in this scheme is:

1 + 2 + ... + N = N(N+1)/2

Now, let's consider the total time taken by this scheme. Since each AND gate takes 1 second to output the resultant signal, the total time taken is equal to the total number of AND gates used. Therefore, the total time taken is:

N(N+1)/2 = (N^2 + N)/2

Now, let's consider the sum of 2^Ti for all i. Since the signals arrive in increasing order of time, we can rewrite this sum as:

2^T1 + 2^T2 + ... + 2^TN = 2^(T1 + 0) + 2^(T1 + 1) + ... + 2^(T1 + N-1)

= 2^T1(1 + 2 + ... + 2^(N-1))

= 2^T1(2^N - 1)

= 2^(T1 + N) - 2^T1

Since T1 < T2 < ... < TN, we can conclude that T1 + N > T1. Therefore, 2^(T1 + N) > 2^T1 and 2^(T1 + N) - 2^T1 > 0. This means that the sum of 2^