디코더는 수신된 코드워드로부터 신드롬 값들을 생성하는 신드롬 연산 블록, 상기 신드롬 값들에 기초하여 에러 위치 다항식을 생성하는 키-방정식 솔버(Key-Equatiion Solver), 상기 에러 위치 다항식에 기초하여 에러 위치를 계산하는 치엔 서치 블록 및 상기 에러 위치에 기초하여 상기 수신된 코드워드의 에러를 정정하여 정정된 코드워드를 출력하는 에러 정정 블록을 포함한다. 상기 신드롬 연산 블록은 상기 신드롬 값들 중 적어도 하나의 홀수 신드롬 값을 병렬로 연산하여 적어도 두 개의 홀수 신드롬 값들을 생성한다.