2006년 1학기        

본 과목은 영어로 강의가 진행됩니다.

• 송홍엽: 2123-4861, B612-613
• hy.song@coding.yonsei.ac.kr      
• http://coding.yonsei.ac.kr/~hysong   

대상:

• 대학원 전기전자공학과 석사과정/박사과정 신입생 
• 통신분야/신호처리분야/네트워크분야
• Basics to the following:
• Error Correcting Codes
• Frequency Hopping Codes
• CDMA Signature Codes
• Public Key Cryptographic Algorithms

• 학부생으로  통신/신호처리/네트워크분야에 관심있는 3.4학년의 수강을 환영
• 이산수학 및 현대대수학의 기초를 다지는 기회
• 추후 응용분야에 대한 소개를 접하는 기회

• 이산수학의 기초:  Numbers, Counting, Groups, Matrix and Linear Transformation
• 유한체 이론
• 유한체이론의 응용 소개: 오류정정부호/암호이론 등등

•   시험 2회:  150점x2회=총 300점
•   Weekly HW:  20점x10회=총 200점
•   Application Project: 50점x2회=총 100점
•   총점 600점
• 상대평가: A=45%, B=50%, 나머지=5%.
• 학부생과 대학원생은 분리평가.
• 학부생이 10명 미만인 경우 절대평가 실시함.

Details

1주 Integers and Congruence

• Congruence mod n
• 1차방정식 mod n
• Chinese Remaindr Theorem
• Fermat's Little Theorem
• Euler's Theorem
• Quadratic Residues mod p
• Quadratic Reciprocity Theorem
• 2차방정식 mod n
• Number theoretic functions/identity

HW#1

2주  (응용) RSA/ElGamal Encryption Algorithms

• Introduction to Public Key Crypto-system
• Probabilistic Primality Testing
• Finding Primitive root mod p -- Gauss Algorithm
• Fast Exponentiation Algorithm
• Introduction to Hash Function
• RSA/ElGamal Encryption Algorithm
• Diffi-Hellman Key Exchange Algorithm
• ElGamal Signature Algorithm

Project #1: Implementation of ElGamal signature algorithm

3주 Groups and Permutations

• Definition
• Subgroup/Normal subgroup
• Cosets/Quotient Group
• Lagrange Theorem
• Order of Element/Group
• Cyclic Group
• Introduction to Permutation Group Sn
• Cycle Structure
• Representation of permutation
• Dihedral Group of Permutations

HW#2

4주 (응용) Burnside and Polya Theory of Counting

• Group Action
• Orbit
• Stabilizer
• Size of Orbit
• Number of Orbits
• Burnside's Lemma on Counting the number of orbits
• Lots of Examples

HW#3

5주 Simultaneous Equations and Vector Spaces

• Homogeneous System of Linear Equations
• Non-homogeneous System of Linear Equations
• Introduction to Vector Spaces over Field
• n-tuple vector space of F_p over F_p
• Subspace
• Basis/Dimension

HW#4

6주 Matrix/Determinants/Linear Transformations

• Linear Transformation on Vector Spaces
• Matrix Representation of Linear Transformation
• Rank of a Matrix
• Determinant of a Matrix as a bi-linear function
• Homomorphism of Vector Spaces
• Isomorphism of Vector Spaces

HW#5

7주 Some Concepts in Modern Algebra

• Polynomial Ring
• Integral Domain
• Euclidean Domain
• Unique Factorization Domain
• Ideal of a Ring/Maximal Ideal/Principal Ideal
• Quotient Ring
• Automorphism Group
• Introduction to Finite Fields

8주 Midterm Exam

9주 Irreducible Polynomials over GF(p)

• Irreducible polynomial over GF(p) and Extension Field
• Finding irreducible polynomials mod p - Sieve method
• Number of irreducible polynomials mod p
• Period of irreducible polynomials mod p
• Rational Cubic Transformation on polynomials over GF(2)
• Primitivity of roots of irreducible polynomials over GF(p)

HW#6

10주 Multiplicative Structure of Finte Fields

• Minimal Polynomial of elements in GF(p^n) over GF(p)
• Properties of minimal polynomial of elements in GF(p^n) over GF(p)
• Cyclotomic Cosets mod p^n -1
• Conjugacy Classes
• Trace Functions and Subfields

HW#7

11주 Additive Structure of Finite Fields

• Additive identity of Finite Field
• Charateristic of a Finite Field
• Factoring of   into irreducible factors over GF(p)
• Polynomial Basis/Normal Basis
• Representation of Elements of finite fields
• Add-one table

HW#8

12주 (응용) Linear Feedback Shift Register Sequences

• Introduction ot Linear Feedback Shift Register
• Connection polynomial is the characteristic polynomial
• Period of output sequence is the period of connection polynomial
• Generating function approach
• Introduction to m-sequences
• Properties of m-sequences

HW#9

13주 (응용) Hamming/BCH Codes - Encoding/Decoding

• Block Codes as Vector Subspace of the n-tuple space of F_p over F_p
• Hamming Distance and Error Correction/Detection Capability of a block code
• Minimum distance decoding and syndrom decoding
• Definitions of Hamming codes and Extended/Shortened Hamming codes
• Encoding and Decoding of Hamming codes
• Definition of Primitive Irreducible double-error-correcting BCH codes
• Encoding and Decoding of BCH Codes

Project #2: Implementation of BCH Encoder/Decoder

14주 (응용) Reed-Solomon Codes - Encoding/Decoding

• Functions on a finite fields
• Fourier Transform - Definition and Properties
• Original Definition of RS Codes and Error Correction Capability
• RS Codes as Special type of BCH Codes
• Transform Domain encoding and decoding

HW#10

15주 (응용) Latin Squares and Finite Projective Planes

• Definition of Latin Squares
• Mutually orthogonal latin squares
• Finite Projective Plane
• Hyper Oval

16주 Final Exam