Sequences in Finite Fields

Current announcements

This space will be used for announcements. Check it regularly.

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 M. Goresky and A. 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 4, 2014.
  Classes end: Thursday December 4, 2014.
  
• Evaluation: There will be three assignments: one is only for finite fields revision (worth 0%), and then two assignments (worth 15% each):

  Assignment	Hand-out Date	Due Date	Worth
  0	Sep. 11	Sep. 30	0%
  1	Sep. 25	Oct. 16	15%
  2	Nov. 6	Nov. 27	15%

  There will be one midterm test (20%) on Thursdays October 23. Moreover, there will be a project (50% of the final mark). The list of possible topics for the project will be distributed by Thursday September 30. Students must pick a topic by Tuesday October 21. A minor report (5% is due on Tuesday November 4). The due date for the project is Thursday December 2 (30%). Oral presentations (15%) will be on the week of December 1-5, 2014.

• Withdrawal: The last day for withdrawal from the course is December 8, 2014. Withdrawals before September 30, 2014, get 100% refund, there is no refund after this date.
• Tentative lecture schedule as of August 2014 (before classes start and subject to change):
  

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




• 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: