×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

### Create a StudySoup account

#### Be part of our community, it's free to join!

or

##### By creating an account you agree to StudySoup's terms and conditions and privacy policy

by: Ms. Helen Sipes

43

0

26

# ADV TOPICS ALGEBRA MATH 690A

Ms. Helen Sipes
ISU
GPA 3.98

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
26
WORDS
KARMA
25 ?

## Popular in Mathematics (M)

This 26 page Class Notes was uploaded by Ms. Helen Sipes on Sunday September 27, 2015. The Class Notes belongs to MATH 690A at Iowa State University taught by Staff in Fall. Since its upload, it has received 43 views. For similar materials see /class/214498/math-690a-iowa-state-university in Mathematics (M) at Iowa State University.

×

## Reviews for ADV TOPICS ALGEBRA

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/27/15
Perfect Codes A Look at Some Current Articles Tim Zick 12 1 04 Class Perfect Codes Basics Z elements are words Distance between words is the number of coordinates where they differ denoted dcc n is the length of the words Any perfect code in Z3 has n 2m 1 C 2nm For any integer n where n 2m 1 there is at least one code of length n with 271 7 elements Equivalence Codes 0 and C are equivalent if C can be created from C by adding a word and a permutation of the coordinates Z3 can be a vector space over Z2 The span of the words in C is denoted by lt C gt The dimension of the subspace lt C gt will be the rank of C de noted rankC as long as OO C Hamming codes are linear sub spaces of Z3 with rank n m Any linear perfect code is equiv alent to the Hamming code If d d1d2 dn is a word we say 239 E d if the ith position of d is a 1 67 corresponds to a word with all zeros except in the ith position If I C 12n then 61 is the word with 1 s in ith position for all iE I The weight of a word c e denoted wc is I Also let lt C gti denote the dual code of the linear span lt C gt For the rest of this presentation we will assume 00O E 0 Lemma 1 If C is a perfect code and d lt C gti then wd n1 2 Proof Let d lt C gtii E d Look at Fz which will be the set of all words of C with weight 3 that contain 239 As d is orthogonal to every word in C and since 239 E d we see that d cl 3 for every 0 E Fz As c c 239 for any c c E Fz and 239 E d the weight of d must be 1 Fz As the union of the set of words of Fz 12n we have our result Lemma 2 Any perfect code C of length n 2m 1 and rank 7 n mp and n m1 g 7 g n 1 there is a partition Ioullu UIt 12 n and Ii lj 2 0 7E j st for each d lt C gti 0 m d Z and for each subset Ijj 12t either 1 Igdor 2 Ij dzw Proof If d d elt C gti then d d lt C gti and from Lemma 1 1 wd wd wd I d n7 1 Consider the base d1 d2 d8 3 n m of the vector space lt C gti Ford 2 1 2 s we can use Lemma 1 and equation 1 to see Idiltu11dvgt 3 4 2 and the Lemma follows from equa tion 2 So the sets IOIlIt form the fundamental partition of the set 12n associated with the code C Let 0 denote the projection of word c on the subspace of Z of Z3 So we can say that c Co01Ct Proposition 1 Let C be a per fect code of length n 2m 1 and of rank 7 n mp Let p Z 2 If the sets IOIlIt for the fundamental partition as sociated with C then any code word c Colcllct of 0 there is a perfect code 000 6 Z O and extended perfect codes 630 6 2339 for z 12t finally if c CO01ct E C then ColcllCv CvClct Q C Proof Let 00 be the set of all words with odd weight of zgv v 12t are orthogonal to those words in lt C gti that contain the set LU As 3 Colcllct of c is orthogonal to all words of lt C gti we get 0 Colcllcv Ovct D As O is a perfect 1 error cor recting code there is to any 0 E 01 with a word of weight 1 st ColCt e E C Then as coct eltlt C gtigti we get that OOoO ltlt C gtigti Suppose a 6 Wu 72 0 Then Eld elt C gti with U g d and k d Z 6 is not orthogonal to d therefore 6 6 IO We proved that for any word 0 of 00 there is an a with we 16 C U st the word c0cv 0 ect E C For any odd word 0 E OEI word of 000 at distance 1 from 0 Thus 000 is an extended perfect code More tools to look at Pefect codes As MDS code of length 75 over the alphabet A 0 a b c is a subset D of At consisting of 475 1 words with minimum dis ta nce two For 23 let 0 0000 a 1100 b 101002 0110 and let G 00001111 For Z3 let 0 OOOa 110b 101c 011 and let G 000111 If AB C 23 let AB a blaE Ab B as usual We want to look at fundamental partitions associated with a per fect code 0 Here rank0 n m2 and 12n IOU IlLJUItI7 Ij D for z 729 t nT4aIo 3711 I2 It 4 Theorem 1 If C is a perfect code in Z3 2 Z Z Z of rank n m 2 there El Ham ming code H of length 75 st each of the words h h1h2 ht E HE an MDS code On of length 75 1 over the alphabet A st 0 UhEHaOa1atla07 quot7at E Dh OOOlOOOhllOOOht Note we will denote C as it is above as CDk Proof So let 0 be a perfect code with length n 2m 1 Tan C39 n m 2 Note that c E C can be uniquely written 3 a0at QOIWIQ75 OOOOOOh1OOOh2OOOht3 where go 6 G g7 E G for z 12t and where the words a0at belong to the alphabet A Let d1d2dg With g m 2 be a vector space in lt C gti By Lemma 2 our fundamental par tition 1011 It associated with 0 either te C di or te dz Z for 239 12g So we can make a g X 75 matrix G bij by 1 if 61 0 if 6 dz Also from Lemma 2 t m 2 1 and the matrix B with be the parity Check matrix of a Ham ming code H As the words a1a2at of Z3 are evenly weighted words we see that equation 3 belongs to 0 iff h1h2ht is orthogonal to the rows of B Let fOl h E HDh denote the set Dh a0a1ata7 E A and aolal OOOhlla1 OOOht E 0 Note that Dh is a code of length 75 1 over the alphabet A As the minimum distance of C is three we get that the minimum distance over Dh is two Here we can say that Dh g 475 From Proposition 1 we see the set G lGlGlG is contained in the kernel of 0 As G GG contains 2t1 words an the Ham ming code H contains ti tl words none of the sets Dhh e H have less than 4 5 words So DhVh E H must be an MDS code We can now calculate the rank of the code CDH Note A is a vector space of dim2 over Z2 dimCDH in Theorem 1 de pends on the linear span of the words of the codes Dhh E H Proposition 2 The rank of the code CDH n m if the codes Dhh E H are all equal to the same linear MDS code in A dimD 2 2t 2 The rank will be n m 1 if the dimension of the linear span of the words in the set lt UhEHDh gt 275 1 If the dimension of the linear span above is equal to 275 then the rank will be n m2 Proof Any word 0 of CDH may be written uniquely as c angh The dimension ofH t 09275 1dimG GG t1 The proposition now comes n by noting that t 1 2 T1

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com