mir.pe (일반/밝은 화면)
최근 수정 시각 : 2025-01-11 22:52:02

FSM

1. 미크로네시아 연방 (Federated States of Micronesia) 의 국가 코드2. 날아다니는 스파게티 괴물 (Flying Spaghetti Monster) 의 줄임말3. 자유 언론 운동 (Free Speech Movement)4. 유한 상태 기계 (Finite State Machine)
4.1. 예시
5. 폴란드의 없어진 자동차 브랜드

1. 미크로네시아 연방 (Federated States of Micronesia) 의 국가 코드

파일:상세 내용 아이콘.svg   자세한 내용은 미크로네시아 연방 문서
를
의 번 문단을
의 부분을
참고하십시오.

2. 날아다니는 스파게티 괴물 (Flying Spaghetti Monster) 의 줄임말

파일:상세 내용 아이콘.svg   자세한 내용은 날아다니는 스파게티 괴물 문서
를
의 번 문단을
의 부분을
참고하십시오.

3. 자유 언론 운동 (Free Speech Movement)

미국 UC 버클리에서 시작된 언론의 자유 운동. 베트남전 당시 언론과 speech에 대한 통제에 대한 반발로, Mario Savio의 주도로 이루어졌다. 현재 UC 버클리에서는 이 일을 기념하는 까페가 도서관 내에 있다.

4. 유한 상태 기계 (Finite State Machine)

''' 이론 컴퓨터 과학
{{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		<colbgcolor=#a36> 이론
기본 대상 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론 #s-4 · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어
계산 복잡도 이론 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
정보이론 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어이론 프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초 정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^ 힙, 피보나치 힙^
수학적 최적화 조합 최적화 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화 내부점 방법 · 경사하강법
선형계획법 심플렉스법
계산 수론 및 암호학 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호
대칭키 암호화 방식 블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
공개키 암호화 방식 공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 }}}}}}}}}



컴퓨터 과학에서 유한 상태 기계(Finite State Machine, FSM)는 컴퓨터의 동작을 모델링하는 데 사용되는 수학적 모델이다. FSM은 유한한 개수의 상태를 가지며, 각 상태에서 특정 동작을 수행하고, 특정 조건에 따라 다른 상태로 전이하도록 설계된다.

FSM과 순서도는 컴퓨터의 동작을 모델링하여 시각적으로 표현하는 도구이지만, 그 목적과 사용 방식에서 차이가 있다. FSM은 상태 변화를 모델링하는 데 유용하며, 순서도는 실행 흐름 또는 처리 과정을 표현하는 데 유용하다.

FSM의 주요 개념은 다음과 같다.
FSM의 상태 수가 과도하게 많으면, 메모리 사용량이 증가하고 설계가 복잡해질 수 있다. 따라서 상태 수를 최소화하고, 상태를 효율적으로 할당하는 것이 중요하다. 순차 논리 회로에서는 implication chart와 같은 방법을 활용하여 불필요한 상태를 줄이고, 원-핫 인코딩(one-hot encoding)과 같은 기법을 통해 상태를 효율적으로 할당하는 등으로 FSM을 효율적으로 만든다.

이론상 FSM은 출력 생성 방식에 따라 무어(Moore) FSM과 밀리(Mealy) FSM으로 나뉜다. 밀리 FSM은 현재 상태와 입력에 의해 출력이 결정되며, 무어 FSM은 현재 상태만으로 출력이 결정된다.

컴퓨터공학에서는 FSM을 명령어, 메모리 등 구체적인 기술과 관련지어 실제 컴퓨터에 적용하는 데 초점을 맞춘다. 반면 오토마타 이론에서는 FSM을 기술적 요소와 독립된 순수한 수학적 모델로 다룬다. 이 두 관점은 서로 접근 방식은 다르지만, 수학적으로 동일한 구조를 공유한다. 오토마타 이론에서 다루는 FSM 내용은 해당 문서를 참고하자.

4.1. 예시

====# 게임 캐릭터의 상태 #====
FSM은 게임 캐릭터의 상태를 정의하는 데 유용하게 활용된다. 예를 들어서, 슈퍼 마리오 월드에서 마리오의 변신 상태를 다음과 같이 FSM으로 표현할 수 있다. 게임 속 변신 상태에 대한 자세한 내용은 해당 문서를 참고하자.

파일:external/www.mariowiki.com/Smw_powerup_chart.jpg

변신 상태 및 능력
변신 방법 (전이 방법)
====# 카운터 #====
카운터(counter)와 같은 순차 논리 회로를 설계할 때도 FSM이 활용된다. 다음은 입력 신호(up_down)에 따라 2-bit 값을 증가시키거나 감소시키는 2-bit 그레이 코드(gray code)[1] 카운터를 FSM으로 나타낸 예시다.

파일:external/rod.info/moore.gif

입력 신호(up_down)가 1이면 출력 신호가 00 → 01 → 11 → 10 → 00 → ... 와 같이 값이 커지는 방향으로 증가하고, 반대로 입력 신호(up_down)이 0이면 출력 신호가 00 → 10 → 11 → 01 → 00 → ... 와 같이 값이 작아지는 방향으로 감소한다.

====# CPU #====
CPU를 설계할 때도 FSM을 활용한다. 다음은 MIPS 아키텍처로 설계된 멀티 사이클 CPU를 fetch(명령어 읽기), decode(명령어 해석), execute(명령어 실행), memory access(메모리 접근), writeback(쓰기)와 같이 5개의 상태로 구성된 FSM으로 모델링한 예시이다. CPU의 상세한 동작 원리는 CPU/구조와 원리 문서를 참고하자.

파일:mips_cpu_fsm.png

상태 별 동작과 전이 순서
  1. fetch 상태: 메모리에서 명령어를 가져옴
    • 다음 상태: decode 상태로 전이됨
  2. decode 상태: 명령어를 해석하고, 필요시 분기 처리를 위한 주소를 계산함
    • 다음 상태: execute 상태로 전이됨
  3. . execute 상태: ALU를 사용하여 연산을 수행하거나 주소를 계산함
    • 다음 상태: decode 상태에서 명령어 해석 결과에 따라서 수행할 연산과 전이될 상태가 달라짐
      • R타입 명령어: ALU 연산 결과를 레지스터에 쓴 후 writeback 상태로 전이됨
      • J타입 명령어: 점프 주소로 이동 후 fetch 상태로 돌아감
      • LOAD 명령어: 메모리 주소 계산 후 memory access 상태로 전이됨
  4. memory access 상태: 명령어 해석 결과에 따라서 메모리에 데이터를 읽거나 씀
    • 다음 상태: writeback 상태로 전이됨
  5. writeback 상태: 연산 결과나 데이터를 레지스터에 저장함
    • 다음 상태: fetch 상태로 돌아감

앞서 CPU의 동작을 간단히 FSM으로 설명했지만, 실제 MIPS는 다양한 명령어를 지원하기 때문에 내부 동작은 훨씬 복잡하다. 그럼에도 불구하고 CPU는 기본적으로 FSM으로 설계할 수 있으며, 각 명령어를 처리하기 위한 상태를 정의하고 이들 상태 간의 전이를 통해 명령어 실행 과정을 제어한다.

5. 폴란드의 없어진 자동차 브랜드

{{{#!wiki style="margin: 0 -10px -5px;"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -6px -1px -11px" 		파일:Centralne Warsztaty Samochodowelogo.png 파일:fsologo.png 파일:Państwowe Zakłady Inżynierii logo.gif 파일:FSM_Logo.png
CWS FSO PZInż FSM
}}}}}}}}} ||


[1] 그레이 코드(grey code)란 인접한 숫자 간에 단 하나의 비트(bit)만 변경되는 이진 코드다. 여러 비트가 동시에 변하지 않고 하나의 비트만 변경되는 특징 때문에 오류 발생 가능성을 줄이는 데 주로 사용된다.

분류