Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

ComCom > Communication Chapter 6 > Flashcards

Communication Chapter 6 Flashcards

1
Q

axioms for a subset to be a subspace

A

(1) C is closed under addition
(2) C is closed under scalar multiplication
(3) C contains the zero vector

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What do you need to do to show is a subset is a subspace for linear codes

A

check the subset is closed under addition

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How to show C is a linear code

A

Check C is a subspace of 𝔽ⁿ₂. Prove C is closed under addition.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Ways to prove C is closed under addition.

A
  • Use dₕ(x,y)=w(x+y)
  • Use dₕ(x,y) = w(x) + w(y) - 2a(x,y)
  • Take all the individual elements of 2 codewords and show manually that addition is closed.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

equivalent basis definition

A

A basis of C is a largest linearly independent set in C

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

dimension of C

A

the size of its basis

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

spanning property

A

every element of the subspace is a linear combination of the elements in the basis.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How to show B is a basis of C.

A

option 1: check the spanning property and linear independence.
option 2: prove dimension is the size of C. Then show B is linearly independent.
option 3: prove dimension is the size of C. Then show B has the spanning property.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How to find the dimension of a basis.

A
  • find |C|=2ᵏ (number of codwords) (lemma 6.7)

- then k=log|C|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

if a set is linearly independent the codewords don’t have…

A

overlapping 1s.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Equation (6.1) c as a linear combination of basis elements

A

c = λ₁c₁+…+λₖcₖ.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Equation (6.1) in terms of the generator matrix B

A

λB = c

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Each ordering of a basis …

A

gives a different generator matrix

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

One generator matrix can be obtained for another by (not equivilence)….

A

performing row operation (changes the basis)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

two equivalent codes have (4)

A
  1. the same length
  2. the same number of codewords
  3. the same dimension
  4. the same minimum distance
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Why do equivalent codes have the same length and the same number of codewords

A

because the dimensions of the generator matrices are the same

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Why do equivalent codes have the same dimension

A

same no. rows => basis is the same size.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Why do equivalent codes have the same minimum distance?

A

permuting columns in a generator matrix maintains all the differences between codewords => same minimum distance.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Not every code has a generator matrix in a normal form but…

A

there exists an equivalent code that admits a normal form.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are parity check matrices good for?

A

determining if a string is in a linear code

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

How to tell if a string is in a linear code

A

If Hxᵀ = 0 then the string is in the linear code

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the parity check matrix given B₀=(Iₖ|A)

A

H=(Aᵀ|Iₙ₋ₖ)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is n in a generator matrix

A

number of columns

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is k in a generator matrix

A

number of rows

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

The minimum hamming distance is the smallest number of…

A

columns in the parity check matrix that form a linearly dependent set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

linearly dependent set of size 1

A

0 string

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

linearly dependent set of size 2

A

2 equal strings (that are multiples of each other)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

how to show x sets are linearly dependent

A

show that one can be written as a sum of the others.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

How to show r is the smallest integer s.t. there exists r linearly dependent columns in H

A
  • find an example for an upper bound (i.e. show a string can be written as a sum of some other strings)
  • find lower bound: if all columns are unique and non-zero no set of ≤2 columns can form a linearly dependent set.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Hamming code of order r

A

linear code whose parity check matrix has 2ʳ-1 columns of length r that are all non-zero.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

How to find the hamming code of order r

A
  • calculate 2ʳ-1
  • find a possible H (with 2ʳ-1 columns that are not repeated and non-zero)
  • input all possible x strings of length 2ʳ-1 to Hxᵀ and choose the x’s which give 0
32
Q

Are hamming codes of order r unique?

A

no

33
Q

What changes a hamming code?

A

the order in which you place the columns of H

34
Q

Switching columns i and j in H changes _____________ in a hamming code

A

switches the ith and jth position in the codeword

35
Q

2 hamming codes of order r are…

A

equivilent

36
Q

Hamming codes have good….

A

transmission rate

37
Q

transmission rate of hamming codes as r->infinity

A

tends to 1

38
Q

Hamming codes are only….

A

1-error-correcting

39
Q

why are hamming codes only 1-error-correcting?

A

because dₕ(c)=3

40
Q

Use of hamming codes in the real world

A

hard drive storage (where errors are unlikely to occur)

41
Q

Given any string, either:

with hamming codes

A
  1. the string is in the code

2. there is always a codewords distance 1 from the string.

42
Q

Hamming decoding scheme for x∈𝔽ⁿ₂

A
  1. calculate s=Hxᵀ
  2. Decode it
    (a) is s=0 then x∈C so return x
    (b) if s≠0 then x is not in C and by prop 6.22 there exists i such that s=hᵢ so return x+eᵢ
43
Q

What is the hamming decoding scheme?

A

a minimum distance decoding

44
Q

what can the hamming decoding scheme do?

A

correct up to 1 error

45
Q

coset informal

A

The coset Q(s) is all strings of length n such that if you take Hxᵀ you get s

46
Q

Q(0)=

A

C

47
Q

For all x,y,∈Q(s) then…

A

x+y∈C

48
Q

Equipartition of 𝔽ⁿ₂

A

The family of subsets {Q(s): s∈𝔽ⁿ⁻ᵏ₂}.

I.e., every string s,s’∈𝔽ⁿ⁻ᵏ₂ is in precisely one of these cosets and cosets are the same size.

49
Q

How to show a given vector is a coset leader of Q(s) for given s and given parity check matrix

A
  1. check the vector is in the coset of S (i.e., check Hxᵀ=s)
  2. Work out the weight of the vector
  3. if s is the zero vector then (0…0)∈Q(s) then the zero vector is the coset leader. Otherwise, work your way up the possible weights of vectors to rule out lower weights and show that the given vector is the coset leader.
50
Q

How to show a coset leader is unique

A

show the other vectors of the same weight and of length n are not in the coset.

51
Q

How to find the cosets for a code C with a given parity check matrix

A

Input all vectors of length n (number of columns) into H Hxᵀ=s.
The cosets are Q(s) for all s just calculated.

52
Q

How to find the syndromes for a code C with a given parity check matrix

A
  1. calculate n-k i.e. the number of rows in H

2. The syndromes are all possible vectors of length n-k

53
Q

what is n-k from the parity check matrix

A

the number of rows in H

54
Q

What is n from the parity check matrix

A

the number of columns in H

55
Q

Method 1 for finding the coset leaders for a code C with a given parity check matrix

A
  1. computer all elements of Q(s) (for all vectors of length n if Hxᵀ=s then x∈Q(s))
  2. choose the vector x with the smallest weight.
56
Q

Method 2 for finding the coset leaders for a code C with a given parity check matrix

A
  1. Study each string of length n of a certain weight (starting with the lowest possible weight)
  2. Check which coset the string is part of Hxᵀ=s
  3. for each coset stop when you find an element which is part of the coset as the weight must be the smallest.
57
Q

Syndrome Decoding Scheme for x∈𝔽ⁿ₂

A
  1. Calculate the syndrome of x, Hxᵀ =s
  2. Choose a coset leader of q(s) of Q(s)
  3. Decode x as x+q(s)
58
Q

syndrome decoding is…

A

a minimum distance decoding

59
Q

If there are two coset leaders then there are two possible….

A

decodings for x.

60
Q

Sphere Covering Bound

A

A(n,d)≥2ⁿ/bⁿₔ₋₁

61
Q

size of H

A

(n-k)xn

62
Q

number of rows in H

A

n-k

63
Q

number of columns in H

A

n

64
Q

vectors are linearly independent if

A

if λ₁c₁+…+λₖcₖ=0 for some λ₁,…,λₖ∈𝔽₂, then λ₁=…=λₖ=0

65
Q

vectors span C if

A

for all c∈C there exists λ₁,…,λₖ∈𝔽₂ s.t. c = λ₁c₁+…+λₖcₖ.

66
Q

permutating columns of B

A

gives an equivalent code

67
Q

permutating rows of B

A

changes the order of the basis

68
Q

r linearly dependent columns in parity check=>

A

minimum hamming distance of C is r (if r is the smallest possible).

69
Q

C defined by parity check matrix

A

C={c∈𝔽ⁿ₂: Hxᵀ = 0}

70
Q

Q(0)

A

C

71
Q

coset leader informal

A

a vector in Q(s) with smallest weight

72
Q

Hamming [7,4] code

A

x∈{0,1}⁴ (x₁+x₂+x₃ mod2) (x₁+x₂+x₄mod2) (x₁+x₃+x₄mod2)

73
Q

number of rows in a generator matrix

A

k

74
Q

number of columns in a generator matrix

A

n

75
Q

More over part for hamming decoding proposition.

A

Moreover, if x is not in C and i is the position where x and c differ then Hxᵀ=hᵢ where hᵢ is the ith column of H.

76
Q

Let C be a hamming code of order r with parity check matrix H, then for every x∈𝔽ⁿ₂ there exists

A

a unique c∈C s.t. dₕ(c,x)<=1

ComCom (27 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions