Here are answers to some questions .... .
Note that the more recent answers are added at the
start .
- As a general comment, I do get a bit tired of referring
questioners back to material that is already in the handouts
....
Please read them, preferably before asking
questions.
Can I ask some about out Q1(5)? Which aspects should we think about
to prove that? Could
you give some hint about the inter-relationship of those two
checking methods? Thank you!
I do not help with bonus questions.
However, look at what actually happens bit by bit.
When we choose the root bridge, which aspect should we firstly consider to
between "Highest Bridge Priority" and "Lowest Bridge Number"? Thank you!
Priority comes first. With equal priorities then test on bridge number.
I have a question about the situation of connecting a LAN with two ports of a
bridge. I think there will no effect in result of our assignment, right?
However, how the frame will be sent then? I mean how the bridge select one
port to send frame or using both of them or more? Is that just depending on
the port ID? And also , how about the situation connecting a LAN using 2 port
in the root direction? I mean how can we select a root port if two ports or
more have same costs to the root bridge? Maybe this situation will never
happen in the real net world!!!???
It is a realistic situation. The lowest numbered port is preferred.
Can you please explain what the 'comments' column in slide 27 (LZW
decompression) of handout 4 mean? It's got th, he, e_, _t etc but where do
these ones come from? Please help.
These can be ignored.
Hi, i have a problem understanding the decoding part of LZW algorithm.
I undestand how the compression works and can follow the example given
in the notes.
So, back to the point, on page 27 we have a decoding example.
Here are my thoughts :
refer to page 27.
1) remember the previous letter , in our case it's none.
2) take letter t (current)
3) deliver letter t.
for the second letter we have :
1) the previous letter is [t]
2) the current letter is [h]
3) deliver the current letter [h]
4) make a new entry [th]
for the third letter we have :
1) the previous letter is [h]
2) the current letter is [e]
3) deliver the current letter [e]
40 make a new entry [he]
{ forth letter omitted , i understand how it's done}
and finally for the fifth letter we have :
1) the previous letter is [_]
2) the curent letter we have [t] <--- So, in the example , we have [th].How do
i calculate this index ?
Could you please explain to me using this example ?
Answer
Except for the recursive entry problem, decoding is very simple indeed.
It is only the encoding that requires lots of tests.
For decoding --
- Remember that LZW transmits dictionary or phrase
indices (usually 12 bit values).
A "phrase" may be a single letter, or several letters.
- When we receive a phrase index, the corresponding phrase is
immediately emitted as the decoded output.
- Then construct a new phrase, being the previous phrase
followed by the first letter of the current phrase, and
add it to the dictionary.
In this case (p27, line 5) the previous phrase is "_" and the current
phrase is "th", so deliver the decoded output "th".
Then create the new phrase "_t", combining the entire previous
phrase "_" and the first letter "t" of the current phrase
"th".
Look at the next step, where the previous phrase "th" is combined with
the first letter of "e", to give the new phrase "the".
For question 1 part 2, I didn't the remainder 0 for this part of question, is
my correct, since the damaged codeword can give a remainder 0, am I right?
I'm a bit confused by your question.
The remainder added as part of the codeword can be zero. With a
5-term generator, the 4-bit remainder can be zero 1/16 of the time.
The remainder from dividing the received codeword must zero if
there is no error (this by construction),
and should be non-zero
if there is a transmisssion error (unless it is the exceptional case of
a non-detected error).
I am reading the Question & Answer. And find one thing is strange.
That is(in 14 April 2004)
In Q2(i), i(x) = 01001011, is the LSB = 0 or LSB = 1 ?
LSB is 1 (Computer convention).
SORRY, I thought I had corrected this one.
The low-numbered bit is to the left, but it is probably confusing
to talk abou "least-significant" and "most significant" bits.
Just write the Hamming bits 1-12 from left to right, and then put the
leftmost data bit in the leftmost Hamming data bit, and so on.
(This correction is copied from later on.)
Q1(i): the division showed remainder = 0, so I appended 0000 as remainder
to the end of i(x) to form c(x), is c(x) = 20-bit long corect ??
Yes, c(x) is 20 bits long.
Q1(iv): when taking the longitudinal parity, only "even" parity gives 4
zeros, which is the same as the remainder, do I have to explain why even
parity works and why it is chosen but not odd parity ??
You don't have to explain, but working out a proper explanation would
probably help your own understanding.
Q2(i): i(x) = 0100 1011 -->> m1 = 0 and m8 = 1 ??
I think this is answered above.
(4) Q4(a): I have done everything graphically, thus there is no need for me
to use the "port[x.y]" convention to describe the end result ?? (bcoz I did it
following the text book)
It should be all right.
Q4(b): the end result should have port[4.3] connected to LAN_E only or
port[4.3&4] connected to LAN_E ??
is port[4.4] redundant bcoz of port[4.3] or they are both needed ??
Questions like this are too close to the answers to be replied to
in public (and possibly in private either!)
Question
Answer
What do you mean ,when you say that"All three of these bit vectors or
ploynomials, v(x), c(x) and e(x), are the same length."<------
The codeword c(x)=i(x)+remainder
But e(x) is of a 7 power only (x^7).
Hence, e(x)=10000001 and lenghts of both e(x)&c(x) are not equal.
So,when we do the addition we just fill all the missing values to the right
with 0's?
Eg. 10110 + 111 = 11101
|
Yours | Correct |
|
10110 | 10110 |
|
00111 | 00111 |
|
------ | ------ |
|
11101 | 10001 |
Am i right?
e(x) must be the same length as c(x) and v(x) and is all zeros,
except for the single 1 where it introduces an error.
But your addition, in the left hand column above, is numeric
(with carries), whereas it should be logical (with no carries),
as in the right column.
The first one : priority of 0(while priority of 20 is the least significant) is
the most significant one , right?
Correct
The second thing is regarding root port cost format.When i determine the
minimal cost from say bridge 4 to bridge 1(root) the cost is 2(consider that
all costs are 1).Now, how do i represent the route?Is port[4,1],port[2,1],port
[1,3] the correct way to do it ?
Use any method that seems reasonable, but please explain it.
First, some questions that occurred several times --
I can't seem to finish off the LZW decoding
You will find that there are one or two characters that cannot be
decided, at the very end.
This is expected, so go as far as you can. (A proper LZW compressor
uses a special End-Of-File code to tidy up at the end.)
Bit ordering, least-significant and most significant bits.
The bits are shown in the order that they are used in forming the
Hamming Code (bit 1 on the left).
(A lot of books do the Hamming code with bit 1 at the right. as for
a computer, so you must be very careful.)
In textbook 3rd edition, page 479, the Network Topology Showing Active Bridge
Connection. what is the dotline stand for? I can not understand why the
dotlines indicate physical but not active connections. Would you please give a
answer in here?
The bridges are physically connected to provide redundant connections,
with several possible routes between most pairs of LANs.
But these extra connections insert possible loops so that messages could
circulate endlessly (remember that a bridge receives ALL of a message
before sending it on).
The whole purpose of the Spanning Tree algorithm is to break these loops
and remove any possibility of circulating messages.
The dotted lines are
the inactive links, which the spanning tree algorithm can reactivate if
the network changes, such as LAN L2 becoming unavailable.
For assignment 3, the question on hamming code, can we use odd parity or even
parity, because it is not stated in the assighment handout, and for showing
that there is an error in bit 7, do we just modify the bit 7, and there prove
it from there?
This is a problem, because there are excellent reasons for both choices.
Even parity results naturally from taking the Exclusive-ORs.
Odd parity ensures that you never send an all-0 codeword, which might
sometimes be an advantage.
Make your own choice.
But as always if in doubt, make a choice and say what you have done.
In Q1(iii), v(x) = c(x)+ e(x); does it mean I have to add them up or just
append e(x) to c(x).
All three of these bit vectors or ploynomials, v(x), c(x) and e(x), are
the same length. Add them up - the 1-bits in e(x) just flip the
corresponding bits in c(x).
In Q2(i), i(x) = 01001011, is the LSB = 0 or LSB = 1 ?
LSB is 1 (Computer convention).
SORRY< I thought I had corrected this one.
Just write the Hamming bits 1-12 from left to right, and then put the
leftmost data bit in the leftmost Hamming data bit, and so on.
In Q4, The higher the priority number, does it really mean the "higher it's
priority"? Bridge 1 priority 5 ; Bridge 2 priority 10; then choose bridge 2
first?
For some strange reason, which may have its roots in Unix, higher
priorities have smaller values. Thus the highest possible
priority is always 0.
I can think of ONE good reason for having low values
associated with a high priority.
If a large numeric value meant a high priority, then a rogue process
could assign an arbitrarily high priority and interfere with the overall
system operation.
With high value meaning low priority, an accidental priority is unlikely
to interfere with general operation.
Can i use format shown on slide 28 rather then the one on slide 25 for the LZW
compression (I find it easier to understand).
Yes, but say so.
Following questions referes to Q4.
Does this mean that we could dismiss the idea of designated ports/bridges,since
all ports have the same cost?
They may still be ranked on port number and bridge number.
I am not sure if we were given rot path costs for Q4.
Are they equal to the bridge IDs OR port number is equal to the its cost?
Neither. The Root Path Cost is approximately the number of bridges traversed.
What is the format we should use to represent a final spaning tree ?
I prefer that you do it as in the handouts, which is closer to the
physical picture. The text draws it as a graph, with circles for all
nodes, whether LANs or bridges. I prefer a more physical form (but if
you have done plenty of Graph Theory you like it as in the bok.)
1)In part(i) of Q2, it said "This question assumes the least_significant bit
to the left,with bits numbered from 1",does that mean c(x)=p1, p2 ,m1, p3, m2,
m3, m4, p4, m5, m6, m7, m8?
Yes
2)In Q3,when we do copression, can we assume ,after the lastest character "U",
a blank will be input and it cause nothing but the emitting of the "U".
See the earlier answer on finishing off compression/decompression.
3)In Q4,does the larger priority number mean higher priority so that "Bridge
1" with priority 0 has lowest piority?
See earlier notes on priorities.
For question 4, the lowest bridgeID become the root bridge, but the bridgeID
has 2 parts priority, and the bridgeID, and first we find highest priority or
the lowest priority to become the root bridge, or the highest priority become
the root bridge, and if they have the same priority, do we then decide that
which should be the root bridge, by finding the lowest bridgeID?
The root bridge is determined only from the bridge number and priority.
This refers to Assignment 2.
For Q1(i), are you sure you give a correct i(x)? no hand-writing error?
Because when i do i(x) mod g(x), i get remainder 00. So, for this case,
c(x) actually equals to i(x), am i right? or just append 00 to i(x)? But
i think it's meaningless to append 00 to data to do CRC, isn't it? I
guess I'm also wrong this time, plz help. thank you Peter!
See the next answer. Don't be surprised if you get a 0 remainder (or
checksum) because with an order 4 generator the remainder should be
zero with a probability of 1/16, and 1/256 for an order 8 generator (9
bits).
In the example on page 17 of lecture notes 4, since i(x)= 1001001,
Why you use 1001001000
(3 more zero appended) to do the i(x) mod g(x)?
The number of zeros added depends on the length of the generator
polynomial.
Here we have a 4 bit polynomial, which must be order 3. [The least
significant bit for x^0 is always a 1, and the coefficient of x^3
(the 4th bit, or most significant bit) is also a 1.]
The number of zeros added is always one less than the number of bits in
the generator.
1. in second question, you ask to show the received message gives a zero
syndrome, what does "syndrome" here refer to? I find the definition
of "syndrome" in lecture note saying "the number locating the error is known as
the syndrome, and is usually zero if no error." But from my understanding, CRC
only can detect error, but cannot find the error position, the "syndrome" is
meaningful for Hamming Code.
Syndrome and remainder (from dividing on reception) are
equivalent here.
where can i find the explanation of "longitudinal parity"?
It is the parity calculated along the message, as in forming the
BCC in the TD800 protocol.
It is a parity character at or near the end of the message.
Compare with "character" parity, which is parity within a character.
It is a single bit added to the character.
(Longitudinal parity is also referred to as
message parity in the handouts.)
"Show that the received message v(x) = c(x) gives a zero syndrome."
Does this really mean "syndrome", or should it be "remainder".
The two are really the same.
- On transmission, add zeros to the end of the information and do
the division.
The remainder becomes the chechsum, replacing the
zeros form the transmitted codeword.
- On reception, divide the entire received codeword by the generator.
The remainder now becomes the syndrome, to check reception.
Only zero/non-zero (or some other yes/no test) is important.
Thus both terms are correct, it is really just how we interpret them.
Use "remainder" if we look from the arithmetic, but "syndrome" if we
look from error checking.