Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes
Hello,

In chapter 7 slide 58, it is said that every middle crossbar number can occur at most once in each row and column, but i don't understand why. It could work out if one is looking after the available number of out and inputs. Am I missing something?

And also: There are multiple solutions for the paull matrix, right? No deterministic way has to be walked?
in * TF "Emb. Sys. and Rob." by (220 points)

1 Answer

+1 vote
 
Best answer
Recall what the meaning of the Paull matrix is: entry (i,j) contains the set of numbers m[i,j] such that the left crossbar i is connected via all k ∈ m[i,j] to the right crossbar j. If crossbar k would occur more than once in a row, e.g., in entries (i,j1) and (i,j2), it would mean that we connect input crossbar i to the middle crossbar k which should then be connected to the two output corssbars j1 and j2. However, that is impossible since the input i of the middle crossbar k is routed either to its output j1 or j2, but not to both.

Analogously, if crossbar k would occur more than once in a column, e.g., in entries (i1,j) and (i2,j), it would mean that we connect input crossbars i1 and i2 to the middle crossbar k which should then be connected to the output corssbar j. However, that is impossible since only either input i1 or i2 of the middle crossbar k can be connected to its output j, but not to both.

Hence, every k∈{0,...,r2−1} can occur at most once in each row and at most once in each column. Do you agree?

For routing in Clos networks, there are many solutions in general. The problem is equivalent to find perfect matchings in bipartite graphs which also has typically more than one solution.
by (170k points)
selected by
Imprint | Privacy Policy
...