Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 POS 형식을 SOP 형식으로 변환하는 프로그램

개요

디지털 논리 회로를 다룰 때 부울 대수식을 SOP(Sum of Products, 곱들의 합) 형식 또는 POS(Product of Sums, 합들의 곱) 형식으로 표현해야 하는 경우가 많습니다. 이 글에서는 Python을 사용해 표준 POS 형식의 부울 식을 동등한 표준 SOP 형식으로 변환하는 방법을 단계별로 살펴봅니다.

문제 정의

문제: POS 형식으로 주어진 부울 식을 동등한 SOP 형식으로 변환합니다.

변환은 먼저 POS 식에 포함된 변수(알파벳)의 개수를 센 뒤, 모든 맥스텀(maxterm)과 민터(minterm)를 계산하는 방식으로 진행할 수 있습니다.

변환 절차 요약

  1. POS 식에서 첫 번째 '.' 구분자 앞부분을 검사하여 변수의 개수를 구합니다.
  2. 각 덧셈 항을 이진수로 해석해 십진수 맥스텀 번호로 변환합니다. 변수에 보수(')가 붙어 있으면 1, 그렇지 않으면 0으로 처리합니다.
  3. 전체 조합(2ⁿ개) 중 맥스텀 목록에 없는 번호를 찾아 민터로 결정합니다.
  4. 각 민터의 이진수 자릿값에 따라 0이면 보수 변수(A'), 1이면 일반 변수(A)로 바꾸고 '+'로 연결하면 최종 SOP 식이 완성됩니다.

구현 예제

# 표준 POS 형식을 표준 SOP 형식으로 변환하는 Python 코드

# 변수의 개수를 계산하는 함수
def count_no_alphabets(POS):
    i = 0
    no_var = 0
    # 첫 번째 '.' 문자 앞의 알파벳 개수가 곧 전체 변수 개수
    while (POS[i] != '.'):
        # 해당 문자가 알파벳인지 확인
        if (POS[i].isalpha()):
            no_var += 1
        i += 1
    return no_var

# 맥스텀(maxterm)을 정수 형태로 계산하는 함수
def Cal_Max_terms(Max_terms, POS):
    a = ""
    i = 0
    while (i < len(POS)):
        if (POS[i] == '.'):
            # 2진수를 10진수로 변환
            b = int(a, 2)
            # 각 맥스텀(정수형)을 리스트에 추가
            Max_terms.append(b)
            # 임시 문자열 초기화
            a = ""
            i += 1
        elif (POS[i].isalpha()):
            # 변수에 보수(')가 붙어 있는지 확인
            if (i + 1 != len(POS) and POS[i + 1] == "'"):
                # 문자열에 '1' 연결
                a += '1'
                # 알파벳 1자리와 ' 기호 1자리만큼 건너뜀
                i += 2
            else:
                # 문자열에 '0' 연결
                a += '0'
                i += 1
        else:
            i += 1
    # 마지막 맥스텀(정수형)을 리스트에 추가
    Max_terms.append(int(a, 2))

# 민터(minterm)를 이진수로 변환한 뒤 최종 SOP 식을 만드는 함수
def Cal_Min_terms(Max_terms, no_var, start_alphabet):
    # 리스트 선언
    Min_terms = []
    # n개의 변수로 만들 수 있는 전체 항의 개수 (2**n)
    max = 2 ** no_var
    for i in range(0, max):
        # 현재 번호가 맥스텀 목록에 없는지 확인
        if (Max_terms.count(i) == 0):
            # 정수를 이진수 문자열로 변환
            b = bin(i)[2:]
            # 이진수 길이를 변수 개수와 같도록 앞에 0을 채움
            while (len(b) != no_var):
                b = '0' + b
            # 민터를 리스트에 추가
            Min_terms.append(b)
    SOP = ""
    # 민터가 남아 있는 동안 반복
    for i in Min_terms:
        # 시작 변수 설정
        value = start_alphabet
        # 이진수의 각 자릿수(0 또는 1)를 검사
        for j in i:
            # 해당 변수가 보수인지 확인
            if (j == '0'):
                # 변수와 보수 기호(')를 연결
                SOP = SOP + value + "'"
            else:
                # 보수가 아닌 변수를 그대로 연결
                SOP = SOP + value
            # 다음 알파벳으로 이동
            value = chr(ord(value) + 1)
        # 항 사이에 '+' 연산자 추가
        SOP = SOP + "+"
    # 마지막에 남은 불필요한 '+' 제거
    SOP = SOP[:-1]
    return SOP

# 메인 함수
def main():
    # 입력 POS 식
    POS_expr = "(A'+B'+C).(A+B+C').(A+B'+C).(A'+B+C)"
    Max_terms = []
    no_var = count_no_alphabets(POS_expr)
    Cal_Max_terms(Max_terms, POS_expr)
    SOP_expr = Cal_Min_terms(Max_terms, no_var, POS_expr[1])
    print("Standard SOP form of " + POS_expr + " ==> " + SOP_expr)

# 드라이버 코드
if __name__ == "__main__":
    main()

출력 결과

Standard SOP form of (A'+B'+C).(A+B+C').(A+B'+C).(A'+B+C) ==>
A'B'C'+A'BC+AB'C+ABC

코드 설명

위 코드는 세 개의 함수로 구성되어 있습니다.

  • count_no_alphabets(): POS 식에서 '.' 구분자가 처음 나오기 전까지의 알파벳을 세어 변수의 개수를 반환합니다.
  • Cal_Max_terms(): 각 덧셈 항을 스캔하면서 보수 변수는 1, 일반 변수는 0으로 치환한 뒤 이진수를 십진수로 변환하여 맥스텀 목록을 만듭니다.
  • Cal_Min_terms(): 0부터 2ⁿ−1까지의 번호 중 맥스텀에 포함되지 않은 번호를 민터로 추출하고, 각 민터의 이진수 자릿값에 따라 보수 여부를 결정해 최종 SOP 식을 문자열로 조립합니다.

모든 변수는 함수 내 지역 범위(local scope)에서 선언되며, 프로그램 실행 흐름에 따라 참조됩니다.

결론

이 글에서는 Python을 활용해 표준 POS 형식의 부울 식을 표준 SOP 형식으로 변환하는 방법을 알아보았습니다. 맥스텀과 민터의 상보적인 관계만 이해하면 어떤 형식의 부울 식이든 손쉽게 다른 형식으로 변환할 수 있습니다. 이러한 변환 기법은 카르노 맵(K-map) 작성이나 논리 회로 간소화 등 디지털 로직 설계의 다양한 분야에서 유용하게 활용됩니다.