Check node update processing for non-binary LDPC (NB-LDPC) architectures requires a large number of clock cycles, which limits the achievable throughput to tens of Mbps for high rate codes. In this work, we propose a new NB-LDPC architecture based on the Trellis-EMS (T-EMS) algorithm that reduces the number of clock cycles by a factor of d <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sub> , by adding an extra column to the trellis. This feature makes our solution the fastest decoder published for NB-LDPC codes, compared to the recent state-of-the-art solutions. Our proposed architecture has been implemented for two different high-rate codes: a (N=3888, K=3456) NB-LDPC over GF(4) and a (N=837, K=726) NB-LDPC over GF(32). The first one achieves a throughput of 3.2 Gbps on a 40nm CMOS process and the second one reaches 484 Mbps on a 90nm CMOS technology.