FSM

최근 수정 시각: 2024-07-30 13:20:36

편집

현재 사용중인 아이피가 ACL그룹 IDC #96574에 있기 때문에 편집 권한이 부족합니다.
만료일 : 무기한
사유 : IDC (AS7524) ITEC Hankyu Hanshin Co.,Ltd.

닫기

분류

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

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

자세한 내용은 미크로네시아 연방 문서 참고하십시오.

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

자세한 내용은 날아다니는 스파게티 괴물 문서 참고하십시오.

3. 자유 언론 운동 (Free Speech Movement)[편집]

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

4. 유한 상태 기계 (Finite State Machine)[편집]

이론 컴퓨터 과학
Theoretical Computer Science

[ 펼치기 · 접기 ]

이론
기본 대상	수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론	재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론	FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어
계산 복잡도 이론	점근 표기법 · 튜링 기계^{고전, 양자, 비결정론적, 병렬 임의접근 기계} · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법)
정보이론	데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(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 문제^미해결 · 콜라츠 추측^미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학

컴퓨터의 수학적 모델의 일종이다. 컴퓨터 내에 유한한 상태를 가지는 기계가 있다고 가정하고, 컴퓨터는 한 순간에 오로지 하나의 상태에만 있을 수 있으며 각 상태별 동작과 상태끼리의 전이에 대한 내용을 설계하게 된다.

요컨대, 순서도와 비슷한 것이며, 공대를 가게 되면 여러모로 써먹게 된다. Moore FSM과 Mealy FSM이 있으며, 밀리 FSM은 상태(state)와 입력에 따라 순서가 결정되고, 무어 FSM은 상태에만 따라 순서가 결정된다.
대개, 시스템이 복잡해지면 복잡해질수록 밀리 쪽은 신경 써야 할 것도 많아지고 감당하기 어려워지기 때문에 무어 FSM을 사용한다.

MIPS로 만든 멀티 사이클 CPU를 예로 설명한다면, Fetch(명령어 읽기), decode(명령어 해석), execute(명령어 실행), memory access(메모리 접근), writeback(쓰기)이 있는데 각각의 동작 방식은 CPU/구조와 원리문서를 참고하기로 하자.

우선, MIPS로 주어진 명령어가 Fetch로 들어가서 주어진 명령을 가져오면서 동시에 PC+4연산을 하는 상태가 된다.(Fetch)

2. 가져온 명령을 해석 해야하는 상태라 ALU가 할 일이 없으니 혹시모를 branch(분기)명령어에 대비해 레지스터의 [15:0]를 shift-left 2해서 pc와 더해놓는다.(decode)
3. 해석 결과에 따라 분기가 달라진다.

3-1. 해석 결과 R타입이다. 그렇다면 rs와 rt연산을 한다. 그 후 4-1로 간다.(execute)
3-2. 해석 결과 j명령어다. 그렇다면 명령하는 대로 점프를 하고 1로 돌아가서 다음 명령을 기다린다..(execute)
3-3. 해석 결과 load다. rs와 [15:0]값을 32bit로 확장시킨 것을 더하고 4-2로 간다.(execute)

4. 분기가 달라진다.

4-1. rs와 rt의 연산 결과를 rd에 쓴다. 그 후 1로 돌아가서 다음 명령을 기다린다(Writeback)
4-2 rs와 [15:0] 확장시켜 나온 주소값에 있는 것을 읽어내고 5로 간다.(memory access)

5 읽어낸 값을 rt에 집어넣고 1로 돌아간다(Writeback)

실제로는 여러 명령어가 있는 만큼 더 복잡해지지만 일단 이런 명령어들을 각각의 상태, 레지스터의 쓰기권한을 켜느냐, 메모리 접근을 가능하게 하느냐, 점프를 하게 하느냐, 같은 상태값을 표현한 순서도를 구현하는 느낌이다. 이쪽은 순서도와는 다르게 Start는 있어도 End는 없지만.

위의 내용들은 컴퓨터공학에 가까운 내용이고, 이것보다 좀 더 추상적인 오토마타 이론에서는 FSM을 명령어, 메모리 같이 기술에 종속된 개념 없이 순수하게 해석하는 편이다. 어차피 두 개념은 기술적으로 동형인데 좀 더 Formal한 설명을 원하면 오토마타 이론 쪽을 보도록 하자.

5. 폴란드의 없어진 자동차 브랜드[편집]

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

[ 펼치기 · 접기 ]

CWS

FSO

PZInż

FSM

이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 및 삽화 제외)
기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.

나무위키는 백과사전이 아니며 검증되지 않았거나, 편향적이거나, 잘못된 서술이 있을 수 있습니다.
나무위키는 위키위키입니다. 여러분이 직접 문서를 고칠 수 있으며, 다른 사람의 의견을 원할 경우 직접 토론을 발제할 수 있습니다.