text:
# Communication complexity

Communication complexity

The notion of communication complexity was introduced by Yao in 1979,[1] who investigated the following problem involving two separated parties (Alice and Bob). Alice receives an n-bit string x[clarification needed] and Bob another n-bit string y[clarification needed], and the goal is for one of them (say Bob) to compute a certain function f(x,y)[clarification needed] with the least amount of communication between them. Note that here we are not concerned about the number of computational steps, or the size of the computer memory used. Communication complexity tries to quantify the amount of communication required for such distributed computations.

Of course they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the function, but the idea here is to find clever ways of calculating f with less than n bits of communication.

This abstract problem is relevant in many contexts: in VLSI circuit design, for example, one wants to minimize energy used by decreasing the amount of electric signals required between the different components during a distributed computation. The problem is also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.

## Formal definition

Let f: X $\times$ Y $\rightarrow$ Z where we assume in the typical case that X = Y = {0,1}n and Z = {0,1}. Alice draws an n-bit string x $\in$ X while Bob draws an n-bit string y $\in$ Y. By communicating to each other one bit at a time (adopting some communication protocol), Alice and Bob want to compute the value of f(x,y) such that at least one party knows the value at the end of the communication. It is trivial to see that once one party knows the answer, with one more bit exchange, both parties know the answer. The worst case communication complexity of this communication protocol, denoted as D(f), is then defined to be

D(f) = minimum number of bits exchanged between Alice and Bob in the worst case

Using the above definition, it is useful to think of the function f as a matrix A (called the input matrix) where each row of the matrix corresponds to x $\in$ X and each column corresponds to y $\in$ Y. An entry in the input matrix is Ax,y = f(x,y). Initially both Alice and Bob have a copy of the entire matrix A (assuming the function f is known to both). Then, the problem of computing the function value can be rephrased as "zeroing-in" on the corresponding matrix entry. This problem can be solved if either Alice or Bob knows both x and y. At the start of communication, the number of choices for the value of the function on the inputs is the size of matrix, i.e. 22n. Then, as and when each party communicates a bit to the other, the number of choices for the answer reduces as this eliminates a set of rows/columns resulting in a submatrix of A.

More formally, a set R $\subseteq$ X $\times$ Y is called a (combinatorial) rectangle if whenever (x1,y1) $\in$ R and (x2,y2) $\in$ R then (x1,y2) $\in$ R. Equivalently, R can also be viewed as a submatrix of the input matrix A such that R = M $\times$ N where M $\subseteq$ X and N $\subseteq$ Y. Consider the case when k bits are already exchanged between the parties. Now, for a particular h $\in$ {0,1}k, let us define a matrix

Th = {(x,y): the k-bits exchanged on input (x,y) is h}

Then, Th $\subseteq$ X $\times$ Y, and Th is a rectangle and a submatrix of A.

### Example: EQ

We consider the case where Alice and Bob try to determine if they both have the same string. That is, we are trying to determine if x is equal to y. It is easy to prove that the equality problem (EQ) will always require you to communicate n bits in the worst case if you want to be absolutely sure x and y are equal. Consider the simple case of x and y being 3 bits. The equality function in this case can be represented by the matrix below. The rows representing all the possibilities of x, the columns those of y.

 EQ 000 001 010 011 100 101 110 111 000 1 0 0 0 0 0 0 0 001 0 1 0 0 0 0 0 0 010 0 0 1 0 0 0 0 0 011 0 0 0 1 0 0 0 0 100 0 0 0 0 1 0 0 0 101 0 0 0 0 0 1 0 0 110 0 0 0 0 0 0 1 0 111 0 0 0 0 0 0 0 1

As you can see, the function only evaluates to 1 when x equals y (i.e., on the diagonal). It is also fairly easy to see how communicating a single bit divides your possibilities in half. If you know that the first bit of y is 1, you only need to consider half of the columns (where y can equal 100, 101, 110, or 111).

Theorem: D(EQ) = n.
Proof. Assume that $D(EQ) \leq n-1$. This means that there exists an (x,x) and an (x',x') having the same history, h. Since this history defines a rectangle, f(x,x') must also be 1. By definition $x \neq x'$ and we know that equality is only true for (a,b) when a = b. Thus, we have a contradiction.

Intuitively, for D(EQ) less than n, we need to be able to define a rectangle in the EQ matrix greater in size than a single cell. All of the cells in this rectangle must contain 1 for us to be able to generalize that this rectangle equals 1. It is not possible to form such a rectangle in the equality matrix.

## Randomized communication complexity

In the above definition, we are concerned with the number of bits that must be deterministically transmitted between two parties. If both the parties are given access to a random number generator, can they determine the value of f with much less information exchanged? Yao, in his seminal paper[1] answers this question by defining randomized communication complexity.

A randomized protocol R for a function f has two-sided error.

$\Pr[R(x,y) = 0] > \frac{1}{2}, \textrm{if }\, f(x,y) = 0$
$\Pr[R(x,y) = 1] > \frac{1}{2}, \textrm{if }\, f(x,y) = 1$

A randomized protocol is a deterministic protocol that uses an extra random string in addition to its normal input. There are two models for this: a public string is a random string that is known by both parties beforehand, while a private string is generated by one party and must be communicated to the other party. A theorem presented below shows that any public string protocol can be simulated by a private string protocol that uses O(log n) additional bits compared to the original.

Note that in the probability inequalities above, the outcome of the protocol is understood to depend only on the random string; both strings x and y remain fixed. In other words, if R(x,y) yields g(x,y,r) when using random string r, then g(x,y,r) = f(x,y) for at least half of all choices for the string r.

The randomized complexity is simply defined as the number of bits exchanged in such a protocol.

Note that it is also possible to define a randomized protocol with one-sided error, and the complexity is defined similarly.

### Example: EQ

Returning to the previous example of EQ, if certainty is not required, Alice and Bob can check for equality using only O(log n) messages. Consider the following protocol: Assume that Alice and Bob both have access to the same random string $z \in \{0,1\}^n$. Alice computes $z \cdot x$ and sends this bit (call it b) to Bob. (The $(\cdot)$ is the dot product in GF(2).) Then Bob compares b to $z \cdot y$. If they are the same, then Bob accepts, saying x equals y. Otherwise, he rejects.

Clearly, if x = y, then $z \cdot x = z \cdot y$, so Probz[Accept] = 1. If x does not equal y, it is still possible that $z \cdot x = z \cdot y$, which would give Bob the wrong answer. How does this happen?

If x and y are not equal, they must differ in some locations:

$x = c_1 c_2 \ldots p \ldots p' \ldots x_n$
$y = c_1 c_2 \ldots q \ldots q' \ldots y_n$
$z = z_1 z_2 \ldots z_i \ldots z_j \ldots z_n$

Where x and y agree, zi * xi = zi * ci = zi * yi so those terms affect the dot products equally. We can safely ignore those terms and look only at where x and y differ. Furthermore, we can swap the bits xi and yi without changing whether or not the dot products are equal. This means we can swap bits so that x contains only zeros and y contains only ones:

$x' = 0 0 \ldots 0$
$y' = 1 1 \ldots 1$
$z' = z_1 z_2 \ldots z_{n'}$

Note that $z' \cdot x' = 0$ and $z' \cdot y' = \Sigma_i z'_i$. Now, the question becomes: for some random string z', what is the probability that Σiz'i = 0? Since each z'i is equally likely to be 0 or 1, this probability is just 1 / 2. Thus, when x does not equal y, Probz[Accept] = 1 / 2. The algorithm can be repeated many times to increase its accuracy. This fits the requirements for a randomized communication algorithm.

This shows that if Alice and Bob share a random string of length n, they can send one bit to each other to compute EQ(x,y). In the next section, it is shown that Alice and Bob can exchange only O(log n) bits that are as good as sharing a random string of length n. Once that is shown, it follows that EQ can be computed in O(log n) messages.

### Public coins versus private coins

It is easier to create random protocols when both parties have access to the same random string (shared string protocol). It is still possible to use these protocols even when the two parties don't share a random string (private string protocol) with a small communication cost. Any shared string random protocol using an n-bit string can be simulated by a private string protocol that uses an extra O(log n) bits.

Intuitively, we can find some set of strings that has enough randomness in it to run the random protocol with only a small increase in error. This set can be shared beforehand, and instead of drawing a random string, Alice and Bob need only agree on which string to choose from the shared set. This set is small enough that the choice can be communicated efficiently. A formal proof follows.

Consider some random protocol P with a maximum error rate of 0.1. Let R be 100n strings of length n, numbered $r_1, r_2, \dots, r_{100n}$. Given such an R, define a new protocol P'R which randomly picks some ri and then runs P using ri as the shared random string. It takes O(log 100n) = O(log n) bits to communicate the choice of ri.

Let us define p(x,y) and p'R(x,y) to be the probabilities that P and P'R compute the correct value for the input (x,y).

For a fixed (x,y), we can use Hoeffding's inequality to get the following equation:

$\Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] \leq 2 \exp(-2(0.1)^2 \cdot 100n) < 2^{-2n}$

Thus when we don't have (x,y) fixed:

$\Pr_R[\exists (x,y):\, |p'_R(x,y) - p(x,y)| \geq 0.1] \leq \sum_{(x,y)} \Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] < \sum_{(x,y)} 2^{-2n} = 1$

The last equality above holds because there are 22n different pairs (x,y). Since the probability does not equal 1, there is some R0 so that for all (x,y):

$|p'_{R_0}(x,y) - p(x,y)| < 0.1$

Since P has at most 0.1 error probability, $P'_{R_0}$ can have at most 0.2 error probability.

## Quantum communication complexity

Quantum communication complexity tries to quantify the communication reduction possible by using quantum effects during a distributed computation.

At least three quantum generalizations of communication complexity have been proposed; for a survey see the suggested text by G. Brassard.

The first one is the qubit-communication model, where the parties can use quantum communication instead of classical communication, for example by exchanging photons through an optical fiber.

In a second model the communication is still performed with classical bits, but the parties are allowed to manipulate an unlimited supply of quantum entangled states as part of their protocols. By doing measurements on their entangled states, the parties can save on classical communication during a distributed computation.

The third model involves access to previously shared entanglement in addition to qubit communication, and is the least explored of the three quantum models.

## Nondeterministic communication complexity

In nondeterministic communication complexity, Alice and Bob have access to an oracle. After receiving the oracle's word, the parties communicate to deduce f(x,y). The nondeterministic communication complexity is then the maximum over all pairs (x,y) over the sum of number of bits exchanged and the coding length of the oracle word.

Viewed differently, this amounts to covering all 1-entries of the 0/1-matrix by combinatorial 1-rectangles (i.e., non-contiguous, non-convex submatrices, whose entries are all one (see Kushilevitz and Nisan or Dietzfelbinger et al.)). The nondeterministic communication complexity is the binary logarithm of the rectangle covering number of the matrix: the minimum number of combinatorial 1-rectangles required to cover all 1-entries of the matrix, without covering any 0-entries.

Nondeterministic communication complexity occurs as a means to obtaining lower bounds for deterministic communication complexity (see Dietzfelbinger et al.), but also in the theory of nonnegative matrices, where it gives a lower bound on the nonnegative rank of a nonnegative matrix.[2]

## Open problems

Considering a 0/1 input matrix $M_f=[f(x,y)]_{x,y\in \{0,1\}^n}$, the minimum number of bits exchanged to compute f deterministically in the worst case, D(f), is known to be bounded from below by the logarithm of the rank of the matrix Mf. The log rank conjecture proposes that the communication complexity, D(f), of Mf is bounded from above by a constant power of the logarithm of the rank of Mf. Since D(f) is bounded from above and below by polynomials of log rank(Mf), we can say D(f) is polynomially related to log rank(Mf). Since the rank of a matrix is polynomial time computable in the size of the matrix, such an upper bound would allow the matrix's communication complexity to be approximated in polynomial time. Note, however, that the size of the matrix itself is exponential in the size of the input.

For a randomized protocol, the number of bits exchanged in the worst case, R(f), is conjectured to be polynomially related to the following formula:

$\min(\textrm{rank}(M'_f): M'_f\in \mathbb{R}^{2^n\times 2^n}, (M_f - M'_f)_\infty\leq 1/3).$

Such log rank conjectures are valuable because they reduce the question of a matrix's communication complexity to a question of linearly independent rows (columns) of the matrix. This reveals that the essence of the communication complexity problem, for example in the EQ case above, is figuring out where in the matrix the inputs are, in order to find out if they're equivalent.

## References

• Kushilevitz, E. and N. Nisan. Communication complexity. Cambridge University Press, 1997.
• Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005
• Dietzfelbinger, M., J. Hromkovic, J., and G. Schnitger, "A comparison of two lower-bound methods for communication complexity", Theoret. Comput. Sci. 168, 1996. 39-51.
• Raz, Ran. "Circuit and Communication Complexity." In Computational Complexity Theory. Steven Rudich and Avi Wigderson, eds. American Mathematical Society Institute for Advanced Study, 2004. 129-137.
• A. C. Yao, "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC, pp. 209–213, 1979. 14
• I. Newman, Private vs. Common Random Bits in Communication Complexity, Information Processing Letters 39, 1991, pp. 67–71.

## Notes

1. ^ a b Yao, A. C. (1979), "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC 14: 209–213
2. ^ Yannakakis, M. (1991). "Expressing combinatorial optimization problems by linear programs". J. Comput. System Sci. 43 (3): 441–466.

• Decision tree complexity

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Complexity theory and organizations — Complexity theory and organizations, also called complexity strategy or complex adaptive organization, is the use of Complexity theory in the field of strategic management and organizational studies. Contents 1 Overview 2 Early research 3 Later… …   Wikipedia

• Communication in small groups — is interpersonal communication within groups of between 3 and 20 individuals.[1] This generally takes place in a context that mixes interpersonal interactions with social clustering. Contents 1 Group communication 1.1 Linear phase model …   Wikipedia

• Communication with extraterrestrial intelligence — (CETI) is a branch of the search for extraterrestrial intelligence that focuses on composing and deciphering messages that could theoretically be understood by another technological civilization. The best known CETI experiment was the 1974… …   Wikipedia

• Communication for sustainable social change and development — involves the use of variety of communication techniques to address inefficient systems, processes, or modes of production within a specific location that has not incurred major technological advances. Different mediums and approaches are used to… …   Wikipedia

• Communication-based train control — (CBTC) is an automated control system for railways that ensures the safe operation of rail vehicles using data communication between various control entities that make up the system.CBTC is a modern successor of the traditional railway signaling… …   Wikipedia

• Complexity economics — Economics …   Wikipedia

• complexity — /keuhm plek si tee/, n., pl. complexities for 2. 1. the state or quality of being complex; intricacy: the complexity of urban life. 2. something complex: the complexities of foreign policy. [1715 25; COMPLEX + ITY] * * * ▪ scientific theory… …   Universalium

• Communication — For the term used in the game of bridge, see Glossary of contract bridge terms # communication. Communication is the activity of conveying meaningful information. Communication requires a sender, a message, and an intended recipient, although the …   Wikipedia

• communication — communicational, adj. /keuh myooh ni kay sheuhn/, n. 1. the act or process of communicating; fact of being communicated. 2. the imparting or interchange of thoughts, opinions, or information by speech, writing, or signs. 3. something imparted,… …   Universalium

• Communication with Extraterrestrial Intelligence — CETI (Communication with Extraterrestrial Intelligence) is a branch of SETI research that focuses on composing and deciphering messages that could theoretically be understood by another technological civilization. The best known CETI experiment… …   Wikipedia


text:
# Chapter 9 - Inequalities and Problem Solving - 9.5 Applications Using Linear Programming - 9.5 Exercise Set - Page 618: 31

$$\frac{3d^3}{2c}$$

#### Work Step by Step

We know the following rules of exponents. $$(1) \ a^m\cdot a^n = a^{m+n} \\ (2) \ (ab)^m =a^mb^m \\ (3) \ (a^m)^n =a^{mn} \\ (4) \ a^{-m} = \frac{1}{a^m} \\ (5)\ \frac{a^m}{a^n} =a^{m-n} \\ (6) \ a^0=1 \\ (7) \ (\frac{a}{b})^m =\frac{a^m}{b^m}$$ Thus, we find: $$\frac{6cd^4}{4c^2d}\\ \frac{3d^3}{2c}$$

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.

format: plain


text:
Home

 Solve any problem (step by step solutions) Input table (Matrix, Statistics)
Mode :
SolutionHelp
Solution
Problem: square root 25 [ Calculator, Method and examples ]

Solution:
Your problem -> square root 25

First find factors of 25
 5 25 5 5 1

25 = 5 × 5

25 = 5^2

sqrt(25) = sqrt(5^2) (Taking squareroot)

= 5

25 is a perfect square

sqrt(25) = 5

Solution steps:
sqrt(25)

=5

Solution provided by AtoZmath.com
Any wrong solution, solution improvement, feedback then Submit Here
Want to know about AtoZmath.com and me


text:
# Topological Phases of Interacting Quantum Systems (19w5034)

## Organizers

(Universitat Erlangen-Nurnberg)

(Yeshiva University)

(Universidad Nacional Autonoma de Mexico)

## Description

The Casa Matemática Oaxaca (CMO) will host the "Topological Phases of Interacting Quantum Systems" workshop in Oaxaca, from June 2, 2019 to June 7, 2019.

There is presently a tremendous activity in the field of topological insulators. There has been a swift progress on understanding the effect of disorder and aperiodicity at the one-particle level, mostly from mathematical physics community, as well as on understanding the effect of interaction in periodic systems, this time mostly from the theoretical physics community. The progress on the effect of both interaction and aperiodicity has been, however, extremely slow. The methods used by these two communities are quite different yet they all make appeal to advance concepts from pure mathematics. The first objective will therefore be to disseminate the important results in the field and to survey its state of the art. The second objective will be a comprehensive survey of the open problems and an honest discussion of the limitations of the present approaches. The third objective will be to connect and integrate the frameworks already used by the researchers and hopefully to put forward proposals with potential for a breakthrough in the problem of topological interacting aperiodic systems. For example, to the present day, $K$-theory, index theory and non-commutative geometry have not yet been applied to interacting systems in a conceptual way and one of the aims of the workshop is to exchange ideas on such matters. The overarching goal of the meeting will be to further intensify the contact between mathematical physicists and theoretical physicists working in the field of topological insulators. This is reflected by the mix of the participants, coming both from physics and mathematics. The organizers have absolutely no doubt that this 5-day conference it will be successful and will have a strong impact on the field, both on an international level, as well as on the local mathematical physics community in Mexico.

The Casa Matemática Oaxaca (CMO) in Mexico, and the Banff International Research Station for Mathematical Innovation and Discovery (BIRS) in Banff, are collaborative Canada-US-Mexico ventures that provide an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station in Banff is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT). The research station in Oaxaca is funded by CONACYT


text:
# cdf of a “mixed” random variable

If $$B$$ is a random variable following a known distribution (in my case $$B$$ follows a Pareto distribution with parameters $$\alpha = 1.5$$ and $$\lambda = 1000$$) and $$R$$ is independent of $$B$$ following a normal distribution of mean $$0.08$$ and standard deviation $$0.2$$. Is there any way to find the cdf of $$X=B \times 1_{\lbrace R \leq -0.1 \rbrace}$$. I tried a lot (by conditionning on the variable $$R$$) and it did not lead me to somewhere. Any hints?

• The distribution of $1_{\{R\,\le\,-1\}}$ is Bernoulli with expected value about $0.1586553$. No information about the distribution of $R$ beyond that is relevant here. ${}\qquad{}$ – Michael Hardy Oct 2 '15 at 0:29

Let $\{A = 0\} = \{R\le -0.1\}$, and $\{A = 1\} = \{R > -0.1 \}$.
Let $P(A = 1) = p$
where $u(x)$ is the step function. You can play with the value of $u(0)$ to make the CDF left or right continuous, whatever your convention may be.


text:
# Applied Statistics Lesson of the Day – Fractional Factorial Design and the Sparsity-of-Effects Principle

Consider again an experiment that seeks to determine the causal relationships between $G$ factors and the response, where $G > 1$.  Ideally, the sample size is large enough for a full factorial design to be used.  However, if the sample size is small and the number of possible treatments is large, then a fractional factorial design can be used instead.  Such a design assigns the experimental units to a select fraction of the treatments; these treatments are chosen carefully to investigate the most significant causal relationships, while leaving aside the insignificant ones.

When, then, are the significant causal relationships?  According to the sparsity-of-effects principle, it is unlikely that complex, higher-order effects exist, and that the most important effects are the lower-order effects.  Thus, assign the experimental units so that main (1st-order) effects and the 2nd-order interaction effects can be investigated.  This may neglect the discovery of a few significant higher-order effects, but that is the compromise that a fractional factorial design makes when the sample size available is low and the number of possible treatments is high.


text:
# Verilog to detect double rising edge

Status
Not open for further replies.

#### Rocketmagnet

##### Junior Member level 3
Hi all,

I am writing my first Verilog program, but I'm finding it quite hard. I just don't understand why it doesn't do what I expect.

Can anyone critique this for me, many thanks. I would really like to get to know Verilog better, so I can write my own peripherals for the Cypress PSoC.

The program should do this (See attached image too):
* If two rising edges are seen on the input (EDGES) within 15 clock cycles the output (CS) goes low.
* If a falling edge is seen on the input, CS goes high.

This is the code I have written so far:

Code:
module CS_Detect (
Counter,
CS,
E,
CLK,
EDGES
);
output [3:0] Counter;    // Used to time the edges
output  CS;              // The main output
output  E;               // A debugging output
// gives a pulse on rising edge of EDGES
input   CLK;
input   EDGES;

reg T;
reg E;
reg CS;
reg Counter;

always @(EDGES or T)
begin
E <= EDGES & !T;
end

always @(posedge CLK)
begin
if (EDGES & !T) begin         // CS Rising
if (Counter > 0) begin    // OMFG, the counter HASN'T timed out. This is the second rising edge!
CS = 0;
end else begin            // Counter has timed out. This is a possible first edge
Counter = 15;
end
end

if (!EDGES & T) begin         // CS Falling
CS = 1;
end

if (Counter > 0) Counter = Counter - 1;

end

always @(negedge CLK)
begin
T       = EDGES;
end

endmodule

#### Attachments

• Double_Rising_Edge.png
3.2 KB · Views: 60

#### lostinxlation

Quick ones.
1. it times out only when EDGE rises.
2. CS value is unknown till EDGE either rises or falls ? The counter has no initial value either.
3. Try to use blocking and non blocking statements properly.
4. your spec, "within 15 clocks" is not very clear. Within 15 clocks from when ?

Last edited:

#### j_andr

##### Full Member level 4
look at my version, I hope it gives an idea how to do the job;
did not test my version on a simulator, may be something needs to be fixed;
Code:
module CS_Detect
(
input      clk, edges,
output reg cs
);

reg [1:0] edges_reg;
reg [1:0] pos_edges;
reg [3:0] cnt;

always @(posedge clk)
edges_reg <= {edges[0],edges}; // just store input, shift-in reg

always @(posedge clk)
if ( edges_reg == 2'b01 )             // if rising edge
pos_edges <= {pos_edges[0], 1'b1}; //  shift in '1'

always @(posedge clk)
if ( pos_edges[0]  )     // if first pos. edge detected
cnt <= cnt + 1'b1;     // incr. the counter
else
cnt <= 4'h0;

always @(posedge clk)
if      ( edges_reg == 2'b10 )           // falling edge
cs <= 1'b1;
else if ( edges_reg == 2'b11 & !(&cnt) ) // 2 rising edges AND
// cnt < 15 (not all cnt bits are HIGH)
cs <= 1'b0;
endmodule

look at your code at the always block, where counter in assigned,

there are to assignments that can happen at the same time:
if (Counter > 0) Counter = Counter - 1;

and

if (EDGES & !T) /.../
Counter = 15;

you will get a synthesis error or the tool will decide how to implement it;

J.A
-------------------------------

a condition to clear 'edges_reg ' has to be added

Last edited:

#### Rocketmagnet

##### Junior Member level 3
1. it times out only when EDGE rises.
That's right. It's only on a rising edge that I'm interested in the time. On a falling edge, CS should always go high.

2. CS value is unknown till EDGE either rises or falls ? The counter has no initial value either.
As a beginner, I'm still not sure how to initialise the values.

3. Try to use blocking and non blocking statements properly.
That's another thing I don't fully understand. I get the general idea, but I'm not exactly sure which I should use, and when.

4. your spec, "within 15 clocks" is not very clear. Within 15 clocks from when ?

I need to detect that there have been two rising edges no more than 15 clocks apart from eachother. I.E. if it ever sees two consecutive rising edges, and the time between them is no more than 15 clocks, then CS goes low.

---------- Post added at 09:55 ---------- Previous post was at 09:53 ----------

look at my version, I hope it gives an idea how to do the job;
did not test my version on a simulator, may be something needs to be fixed.

Thanks. I'll try it out tonight.

#### Rocketmagnet

##### Junior Member level 3
On closer examination, this code cannot be correct.

Code:
 always @(posedge clk)
edges_reg <= {edges[0],edges}; // just store input, shift-in reg

I assume you meant:

Code:
 always @(posedge clk)
edges_reg <= {edges_reg[0],edges}; // just store input, shift-in reg

Furthermore, the Counter is only ever incremented on a rising edge, therefore it is unable to count the number of clocks between rising edges.

I think the problem is that I didn't describe the behaviour properly. Let me try again:

Rule 1: Whenever a falling edge is seen, the output goes high.
Rule 2: Whenever a rising edge is seen, if another rising edge was also seen no more than 15 clock cycles previously, then the output goes low.

I hope that is unambiguous. Please also see the waveform attached to the original post.

Many thanks

Hugo

#### FvM

##### Super Moderator
Staff member
Some additional comment on the original code:
- reg Counter must be changed to reg [3:0] Counter, otherwise, Counter is only synthesized with one bit
- the below comment is wrong and misunderstanding how sequential blocks are evaluated:
there are to assignments that can happen at the same time:
if (Counter > 0) Counter = Counter - 1;
and
if (EDGES & !T) /.../
Counter = 15;
you will get a synthesis error or the tool will decide how to implement it;
You don't get a synthesis error, the code has no problem in this regard
- The original edge detection is incorrect in so far, that it's only sensitive to transitions between the negative and the positive edge, which seems not to correspond to the specification
- The edge detection scheme suggested by j_andr (despite of the mentioned syntax error) is basically on the right track. I didn't however analyze his code completely, I think it has other errors, too. Particularly, it doesn't succeed in making a 15 clocks interval to accept two edges.

j_andr

### j_andr

Points: 2

#### Rocketmagnet

##### Junior Member level 3
You don't get a synthesis error, the code has no problem in this regard.

That is correct, my code synthesises, but does not function according to spec.

- The original edge detection is incorrect in so far, that it's only sensitive to transitions between the negative and the positive edge, which seems not to correspond to the specification.

No. There is code there to detect both types of edge. See the "// CS Falling" and "// CS Rising" comments.

- The edge detection scheme suggested by j_andr (despite of the mentioned syntax error) is basically on the right track.

To me is seems wrong because it only seems to be sensitive to the first two rising edges ever, not to all rising edges.

Please see the image attached to my original post.

Many thanks
Hugo

#### FvM

##### Super Moderator
Staff member
Please see the image attached to my original post.
You don't need to repeat this mantra-like statement. I think, I basically understood the intention of your specification, although the specification isn't very clear, as others already mentioned.
No. There is code there to detect both types of edge. See the "// CS Falling" and "// CS Rising" comments
I see, that my comment wasn't clear enough. But you also didn't take the effort to think about it, although you already experienced problems with your code.
I said your code is "only sensitive to transitions between the negative and the positive edge". Here I meant signal ("EDGE") transitions and clock ("CLK") edges. The wrong point is to use CLK negedge and posedge. If you consider thoroughly, what your code is doing, you'll get the point. If EDGE changes it's state between CLK rising and falling edge, the event is ignored.
To me is seems wrong because it only seems to be sensitive to the first two rising edges ever, not to all rising edges.
Yes, I mentioned that the code has errors. The basic edge detection scheme is correct, not the way how it's acting on first or second one. You'll find the basic concept, shifting the input signal into a chain of two, better three registers on one clock edge, in many applications.

#### j_andr

##### Full Member level 4
FvM said:
You don't get a synthesis error, the code has no problem in this regard
you are right, I was wrong, quartus compiled it smoothly;
have to write slightly slower, think a little bit longer;

the first example was written too fast,
but have a better version, it at least compiles without errors;
and is witty I think;
Code:
module CS_Detect
(
input      clk, edges,
output reg cs
);

reg  edges_reg = 1'b1;

always @(posedge clk)
edges_reg <= edges;

wire pos_pulse = edges & !edges_reg;

reg [14:0] train;

always @(posedge clk)
train <= {train[13:0], pos_pulse};

always @(posedge clk)
if      ( !edges )                      cs <= 1'b1;
else if ( train != 15'h0 && pos_pulse ) cs <= 1'b0;

endmodule

if 'edges' signal is asynch. to clk it has to be latched twice
and 'pos_pulse' should use latched input to detect L to H transition;

----
J.A

Last edited:
shyam4908

### shyam4908

Points: 2

#### shyam4908

##### Newbie level 6
module CS_Detect
(
input clk, edges,
output reg cs
);

reg d_edges;
wire pos_edge;
reg pos_db_edge := '0' ;

//Delay the edges signal
always@(posedge clk)
d_edges <= edges;

//postive edge detection
pos_edge = edges && !d_edges;
neg_edge = !edges && d_edges;

//number of posedge
always@(posedge clk)
if (pos_db_edge == '0' and pos_edge = '1')
pos_db_edge <= '1';
else (pos_db_edge == '1' and pos_edge = '1')
pos_db_edge <= '0'

always@(posedge clk)
d_pos_db_edge <= pos_db_edge;

//double detection
pos_db_edge_pulse = !pos_db_edge && d_pos_db_edge;

always@(clk)
if (neg_edge = '1' )
CS <= '1' ;
else if (pos_db_edge_pulse = '1')
CS <= '0'

Thanks
Shyam

endmodule

#### FvM

##### Super Moderator
Staff member
@j_andr: Your second solution is pretty straightforward, but it uses slightly more registers and logic cells than a counter approach. It can be accepted with a window length of 15, I think. The double registering of asynchronous inputs is very import, because nasty random errors are brought up, if you ignore it. It's often done by shifting the input into a 2-bit SR.

@shyam4908: Whatever your code does, it's missing a means to detect two events within a 15 clocks window, either a counter or a SR, as j_andr suggested. Thus it can't keep the specification.

#### Rocketmagnet

##### Junior Member level 3
Hi, thanks for the new code.

Code:
 always @(posedge clk)
train <= {train[13:0], pos_pulse};

always @(posedge clk)
if      ( !edges )                      cs <= 1'b1;
else if ( train != 15'h0 && pos_pulse ) cs <= 1'b0;

Isn't there a chance here that train will always be 0x01 during the last if statement?

The problem I see with this approach is that a valid train looks like:
* 0001111110000000

and an invalid train looks like:
* 1111111110000000

So to be valid:
* train must be non-zero
* train[14] must be zero
* train[0] must be set after train is tested for validity.

Perhaps it should be:
Code:
 always @(posedge clk)
if      ( !edges )                           cs <= 1'b1;
else if ( !train[14] && train && pos_pulse ) cs <= 1'b0;

always @(posedge clk)
train <= {train[13:0], pos_pulse};

I'll try this tonight when I get home from work.

Many thanks again
Hugo

#### FvM

##### Super Moderator
Staff member
The problem I see with this approach is that a valid train looks like:
* 0001111110000000

and an invalid train looks like:
* 1111111110000000
Sounds like you misunderstood the code. Both cases can't happen because a "one" in the train SR is marking a rising edge of the EDGE input rather than a high state. You'll have exactly a single "one" in the train register, when the logic triggers.

P.S.: Exact fall back condition and possible retriggering hasn't been specified yet.

#### Rocketmagnet

##### Junior Member level 3
Sounds like you misunderstood the code. Both cases can't happen because a "one" in the train SR is marking a rising edge of the EDGE input rather than a high state. You'll have exactly a single "one" in the train register, when the logic triggers.

Aah, yes. Sorry. I missed that.

P.S.: Exact fall back condition and possible retriggering hasn't been specified yet.

I'm sure it has:
Rule 1: Whenever a falling edge is seen, the output goes high.
Rule 2: Whenever a rising edge is seen, if another rising edge was also seen no more than 15 clock cycles previously, then the output goes low.

P.S. Did you look at the attached image?

Hugo

#### FvM

##### Super Moderator
Staff member
P.S. Did you look at the attached image?
Yes, as already mentioned. And although you possibly think, it doesn't clearly specify all cases. The latest text however does, as far as I see.
- The waveform neither shows the clock nor defines what's exactly considered a clock cycle. Your initial code demonstrates, why this matters.
- It suggests a fall-back condition, but doesn't claraify, if it's e.g. valid also during the 15 clocks window
So all implementations have been partly based on guesses.

#### Rocketmagnet

##### Junior Member level 3
- The waveform neither shows the clock nor defines what's exactly considered a clock cycle. Your initial code demonstrates, why this matters.
- It suggests a fall-back condition, but doesn't claraify, if it's e.g. valid also during the 15 clocks window
So all implementations have been partly based on guesses.

That's a good point. Fortunately, it's not super critical. Anything outside the spec can cause undefined behaviour (as long as it doesn't start WWIII). This function only really needs to distinguish between two types of event: a double rising edge, and a single rising edge. The double rising edges will always be much closer together than 15 clocks, and the single rising edges will always be much further apart than 15 clocks. There will never be any borderline cases, e.g. where the two rising edges are exactly 15 clocks apart.

The falling edges will always be outside of the 15 clock period.

Anyway, I'll try the "train" code tonight.

Hugo

#### j_andr

##### Full Member level 4
/.../
So to be valid:
* train must be non-zero
* train[14] must be zero
* train[0] must be set after train is tested for validity.

Perhaps it should be:
/.../

may be I'm wrong but sounds like you think the order of 'always' block
has any meaning in rtl description; it's false assumption;
J.A

#### Rocketmagnet

##### Junior Member level 3
but have a better version, it at least compiles without errors;

Haha! It works!

Thanks guys, you have been very helpful, and I have learned a lot with my first verilog project. There was only one problem, which is that the synthesiser
didn't like the initalisation of edges_reg, so I left it uninitialised.

I think I will try to modify it use a counter, rather than a shift register, because I may want the time limit to be much longer in the future.

If you're interested in what I'm going to use it for, this will be going into a PSoC 3, which will be sampling data for a micro sized 6-axis force sensor. Eventually, I hope to install them in the finger tips of our robot hand.

Many thanks again everyone for all your help.

Hugo

#### Rocketmagnet

##### Junior Member level 3
I think I managed to do it with a counter in the end. Here's the code:

Code:
module CS_Detect (
CS,
CLK,
EDGES
);
output  CS;
input   CLK;
input   EDGES;

reg  edges_reg;
reg [3:0]  Counter;
reg CS;

wire  pos_pulse =  EDGES & !edges_reg;
wire  neg_pulse = !EDGES &  edges_reg;

always @(posedge CLK)
begin
edges_reg <= EDGES;
if (pos_pulse == 1) begin
Counter <= 15;
end else begin
if (Counter > 0) Counter <= Counter - 1;
end
end

always @(posedge CLK)
begin
if ((pos_pulse == 1) && (Counter > 0)) begin
CS <= 0;
end else begin
if (neg_pulse == 1) begin
CS <= 1;
end
end
end

endmodule

Many thanks again for all you taught me.

Hugo

#### FvM

##### Super Moderator
Staff member
Looks good in general. If EDGE is asnychronous to clk, you should observe what's said about double registering. Otherwise, random errors can occur, either triggering of the output on first pulse or ignorance of input events.

Status
Not open for further replies.


text:
# Related rates 2

#### ayahouyee

##### New member

A tightrope is 40 ft above ground between two buildings that are 60 feet apart. A
tightrope walker starts along the rope and walks from building A to building B at
a rate of 2 feet per second. 80 feet above the starting point of the tightrope walker
on building A is a spotlight that is illuminating the tightrope walker as the tightrope
walker is crossing between the two buildings.

(a) How fast is the shadow of the tightrope walker's feet moving along the ground
when the tightrope walker is midway between the buildings?

(b) How fast is the shadow of the tightrope walker's feet moving up the wall of building
B when the tightrope walker is twelve feet away from building B?

#### MarkFL

Can you use similarity of triangles to express $s$ as a function of $x$?