Sequences in Finite Fields

General Information

• Course objectives: to study sequences and feedback shift registers over finite fields, as well as, their properties and applications in cryptography and communications.
• Textbook:
  • ``Signal Design for Good Correlation'', by S. Golomb and G. Gong, Cambridge University Press, 2005.
  Other textbooks that will be used:
  • ``Algebraic Shift Register Sequences'', by Mark Goresky and Andrew Klapper , Cambridge University Press, 2012.
  • ``Shift Register Sequences'', by S. Golomb, Aegean Park Press, 1982.
  • ``Finite Fields'', Chapter 8, by R. Lidl and H. Niederreiter, Cambridge University Press, 1997.
  • ``Introduction to Finite Fields and their Applications'', Chapter 6, by R. Lidl and H. Niederreiter, Cambridge University Press, 1994.
  All the above books are available at Carleton's library.
• Prerequisites: a course in finite fields like MATH 4109 or equivalent; or permission of the School.
• Classes begin: Thursday September 8, 2016.
  Classes end: Thursday December 8, 2016.
  
• Evaluation: There will be three assignments: one is only for finite fields revision (worth 5%), and then two sequences assignments (worth 15% each):

  Assignment	Hand-out Date	Due Date	Worth
  0	Sep. 15	Oct. 6	5%
  1	Sep. 29	Oct. 20	15%
  2	Nov. 10	Dec. 1	15%

  There will be one midterm test (20%) on Thursdays November 17.

  Moreover, there will be a project (45%). The list of possible topics for the project will be distributed by Thursday October 6. Students must pick a topic by Thursday November 3. A minor report (5% is due on Thursday November 10). The due date for the project is Thursday December 1 (25%). Oral presentations (15%) will be on the week of December 5-9, 2016.

• Withdrawal: The last day for withdrawal from the course without academic penalties is the last day of classes.
• Tentative lecture schedule as of August 2016 (before classes start and subject to change):
  

WEEK	DATES	LECTURES	REMARKS
*	Sep. 8	Introduction to the course. Sequences over finite fields and applications. Feedback shift registers and linear feedback shift registers.
1	Sep. 12-16	LFSR: examples; periodic properties; polynomial view.	Finite fields material distributed (Sep. 13); exercises handed out (Sep. 15).
2	Sep. 19-23	LFSR: minimal polynomials and periods.
3	Sep. 26-30	LFSR: irreducible and reducible decomposition; matrix representation.	Assignment 1 handed out (Sep 29).
4	Oct. 3-7	LFSR: traces representation; decimation; generating function.	Exercises of finite fields due (Oct 6). List of projects distributed (Oct 6).
5	Oct. 10-14	Randomness criteria. Golomb's postulates for binary and q-ary sequences. Short introduction to characters.
6	Oct. 17-21	Characters (cont). Randomness of m-sequences.	Assignment 1 due (Oct. 20).
7	Oct. 24-28	Reading week
8	Oct. 31 - Nov. 4	Randomness of m-sequences (cont). Interleaved sequences.	Project topic chosen (Nov. 3).
9	Nov. 7-11	Discrete Fourier transform of periodic sequences. Trace representation.	Minor project due (Nov. 10). Assignment 2 handed out (Nov. 10).
10	Nov. 14-18	Trace representation (cont). DFT and linear span of a sequence. Berlekamp-Massey algorithm.	Midterm Test (Nov. 17).
11	Nov. 21-25	Crosscorrelation functions. Signal sets. Hadamard and Walsh transforms.
12	Nov. 28 - Dec. 2	Gold-pair and other signal sets.	Assignment 2 due (Dec. 1). Project due (Dec. 1).
13	Dec. 5-9	Project presentations (in class).




• Academic Accommodation:
You may need special arrangements to meet your academic obligations during the term. For an accommodation request the processes are as follows:
• Pregnancy and Student Parental Leave: write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details see the Parental Leave Guide.
• Academic Accommodations for Students with Disabilities: The Paul Menton Centre for Students with Disabilities (PMC) provides services to students with Learning Disabilities (LD), psychiatric/mental health disabilities, Attention Deficit Hyperactivity Disorder (ADHD), Autism Spectrum Disorders (ASD), chronic medical conditions, and impairments in mobility, hearing, and vision. If you have a disability requiring academic accommodations in this course, please contact PMC at 613-520-6608 or pmc@carleton.ca for a formal evaluation. If you are already registered with the PMC, contact your PMC coordinator to send me your Letter of Accommodation at the beginning of the term, and no later than two weeks before the first in-class scheduled test or exam requiring accommodation (if applicable). After requesting accommodation from PMC, meet with me to ensure accommodation arrangements are made. Please consult the PMC website for the deadline to request accommodations for the formally-scheduled exam (if applicable).
• Religious obligation: write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details see the Religious Observation Guide.

Contact Information: