# M-수열 (Maximum-Length Sequence, M-Sequence)

M-수열(최대 길이 수열, maximum-length sequence)은 특성 다항식이 원시 다항식인 선형 재귀를 만족하는 (0이 아닌) 이진 수열입니다. n단 선형 피드백 시프트 레지스터(LFSR)로 만들 수 있는 가장 긴 주기 2^n−1을 가집니다.

## M-수열의 구성 요소

- **이진 수열:** 0과 1로만 구성됩니다.
- **0이 아님:** 초기 상태가 모두 0이면 수열도 계속 0이므로 제외합니다. 0이 아닌 초기 상태에서는 n비트 상태가 0이 아닌 2^n−1가지 값을 모두 한 번씩 거친 뒤 반복됩니다.
- **선형 재귀:** 각 항은 이전 n개 항 일부의 XOR(GF(2) 위의 덧셈)로 정해집니다.
- **원시 특성 다항식:** 재귀 관계를 정의하는 다항식이 원시 다항식입니다. 즉 유한체에서 더 간단한 다항식으로 인수 분해되지 않을 뿐 아니라(기약), 그 근이 확대체 GF(2^n)의 곱셈군 전체를 생성합니다. 다항식이 원시적이어야 주기가 최대 길이가 됩니다.

## 예

원시 다항식 x^3 + x + 1에 대응하는 재귀 sk+3 = sk+1 ⊕ sk에서 초기 값 1, 0, 0으로 시작하면 1001011이 나오고, 이 7비트(2^3−1 = 7)가 계속 반복됩니다.

빛의 깜박임으로 배에 신호를 보내는 등대에 비유할 수 있습니다. 깜박임은 빛(1)과 빛 없음(0) 두 가지이고, 각 깜박임은 이전 몇 번의 깜박임으로 정해지며, 한 주기 안에서는 불규칙해 보이지만 정확히 같은 패턴이 반복됩니다.

## 주요 성질

- **균형성:** 한 주기 안에 1이 2^n−1개, 0이 2^n−1−1개 있어 0과 1의 분포가 거의 같습니다.
- **자기 상관 특성:** 0과 1을 ±1로 바꾸어 보면 주기 자기 상관이 위상이 맞을 때 N(= 2^n−1), 그 밖에서는 −1인 두 값만 가집니다. 그래서 동기화와 신호 구분이 필요한 신호 처리에 적합하고, 스펙트럼이 거의 평탄합니다.
- **의사 난수성:** 결정론적이지만 통계적으로는 무작위에 가깝게 보여 시뮬레이션과 테스트에 쓰입니다.
- **오류 정정 부호와의 관계:** M-수열의 한 주기와 그 순환 이동들은 심플렉스 부호의 부호어를 이룹니다.
- **생성의 단순성:** LFSR 하나로 쉽게 만들 수 있어 하드웨어 구현이 간단합니다. 원시 다항식을 바꾸면 다른 M-수열을 얻습니다.

## 한계

- **암호학적 안전성 부족:** 생성 규칙이 선형이므로, 길이 n인 LFSR이 만든 수열은 연속된 2n비트만 알면 벌리캠프-매시(Berlekamp–Massey) 알고리즘으로 생성 규칙 전체를 복원할 수 있습니다. 따라서 단독으로는 암호용 키 스트림으로 쓸 수 없습니다.
- **초기 상태 의존:** 출력은 초기 상태에 따라 수열의 어느 위치에서 시작하는지가 정해지므로, 송수신 양쪽이 같은 초기 상태와 위상을 맞춰야 합니다.
- **회로 규모:** LFSR 자체는 간단하지만, 긴 수열이나 여러 채널을 구현하면 전체 회로가 커집니다.

## 응용 분야

- **통신:** CDMA 같은 확산 스펙트럼 시스템에서 신호를 넓은 대역에 확산시키는 데 사용되며, GPS의 C/A 코드는 M-수열 두 개를 결합한 골드 부호입니다.
- **신호 처리:** 알려진 자기 상관 특성 덕분에 시스템 식별, 채널 추정, 음향 측정에 활용됩니다.
- **암호:** 스트림 암호에서는 LFSR을 단독으로 쓰지 않고, 여러 LFSR을 비선형 함수나 불규칙 클로킹과 결합해 키 스트림을 만들어 왔습니다(GSM의 A5/1 등).

---
출처: https://achivx.kr/glossary/m-sequence-m-%EC%88%98%EC%97%B4/ · ACHIVX 용어 사전 · 수정일 2026-10-20